Best shuffle: Difference between revisions

Content added Content deleted
(Updates D entries, tags)
Line 1,051: Line 1,051:


=={{header|D}}==
=={{header|D}}==
===Simpler Version===
{{works with|D|2}}
Translation of [[Best_shuffle#Icon_and_Unicon|Icon]] via [[Best_shuffle#AWK|AWK]]
Translation of [[Best_shuffle#Icon_and_Unicon|Icon]] via [[Best_shuffle#AWK|AWK]]
<lang d>import std.stdio, std.random, std.algorithm, std.conv, std.range,
<lang d>import std.stdio, std.random, std.algorithm, std.conv, std.range,
std.typecons;
std.typecons;

auto bestShuffle(in dstring o){
auto bestShuffle(in dstring o) {
auto s = o.dup;
auto s = o.dup;
randomShuffle(s);
s.randomShuffle();

⚫
foreach (i, ref ci; s) {
foreach (i, ref ci; s) {
if (ci != o[i])
if (ci != o[i])
continue;
continue;
foreach (j, ref cj; s)
foreach (j, ref cj; s)
if (ci != cj && ci != o[j] && cj != o[i]) {
if (ci != cj && ci != o[j] && cj != o[i]) {
swap(ci, cj);
swap(ci, cj);
Line 1,070: Line 1,070:
}
}


return tuple(s, count!q{ a[0] == a[1] }(zip(s, o)));
return tuple(s, zip(s, o).count!q{ a[0] == a[1] }());
⚫
} unittest {
}

⚫
unittest {
assert(bestShuffle("abracadabra"d)[1] == 0);
assert(bestShuffle("abracadabra"d)[1] == 0);
assert(bestShuffle("immediately"d)[1] == 0);
assert(bestShuffle("immediately"d)[1] == 0);
Line 1,084: Line 1,082:
}
}


void main(string[] args) {
void main(/*in*/ string[] args) {
if (args.length > 1) {
if (args.length > 1) {
string entry = join(args[1 .. $], " ");
string entry = args[1 .. $].join(" ");
auto res = bestShuffle(to!dstring(entry));
auto res = entry.dtext().bestShuffle();
writefln("%s : %s (%s)", entry, res[0], res[1]);
writefln("%s : %s (%d)", entry, res.tupleof);
}
}
}</lang>
}</lang>
===Alternative version===
===Faster Version===
<lang d>import std.stdio, std.algorithm, std.range;
<lang d>import std.stdio, std.algorithm, std.range;

extern(C) pure nothrow void* alloca(in size_t size);
extern(C) pure nothrow void* alloca(in size_t size);

pure nothrow void bestShuffle(in char[] txt, char[] result) {
void bestShuffle(in char[] txt, ref char[] result) pure nothrow {
// Assume alloca to be pure.
//extern(C) pure nothrow void* alloca(in size_t size);
enum size_t NCHAR = cast(size_t)char.max + 1;
enum size_t NCHAR = cast(size_t)char.max + 1;
enum size_t MAX_VLA_SIZE = 1024;
enum size_t MAX_VLA_SIZE = 1024;
Line 1,102: Line 1,102:
if (len == 0)
if (len == 0)
return;
return;

// txt and result must have the same length
// txt and result must have the same length
// allocate only when necessary
// allocate only when necessary
if (result.length != len)
if (result.length != len)
result.length = len;
result.length = len;

// how many of each character?
// how many of each character?
size_t[NCHAR] counts;
size_t[NCHAR] counts;
Line 1,117: Line 1,117:
}
}
assert(fmax > 0 && fmax <= len);
assert(fmax > 0 && fmax <= len);

// all character positions, grouped by character
// all character positions, grouped by character
size_t* ptr1 = null;
size_t[] ndx1;
⚫
{
if ((len * size_t.sizeof) < MAX_VLA_SIZE)
ptr1 = cast(size_t*)alloca(len * size_t.sizeof);
size_t* ptr1;
size_t[] ndx1 = (ptr1 == null) ? new size_t[len] : ptr1[0..len];
if ((len * size_t.sizeof) < MAX_VLA_SIZE)
for (size_t ch = 0, i = 0; ch < NCHAR; ch++)
ptr1 = cast(size_t*)alloca(len * size_t.sizeof);
// If alloca() has failed, or the memory needed is too much
⚫
if (counts[ch])
foreach (size_t j, char c; txt)
// large, then allocate from the heap.
if (c == ch) {
ndx1 = (ptr1 == null) ? new size_t[len] : ptr1[0 .. len];
}
⚫
ndx1[i] = j;
{
⚫
i++;
}
int pos = 0;
foreach (size_t ch; 0 .. NCHAR)
⚫
if (counts[ch])
foreach (j, char c; txt)
if (c == ch) {
⚫
ndx1[pos] = j;
pos++;
⚫
}
}

// regroup them for cycles
// regroup them for cycles
size_t* ptr2 = null;
size_t[] ndx2;
{
if ((len * size_t.sizeof) < MAX_VLA_SIZE)
ptr2 = cast(size_t*)alloca(len * size_t.sizeof);
size_t* ptr2;
size_t[] ndx2 = (ptr2 == null) ? new size_t[len] : ptr2[0..len];
if ((len * size_t.sizeof) < MAX_VLA_SIZE)
for (size_t i = 0, n = 0, m = 0; i < len; i++) {
ptr2 = cast(size_t*)alloca(len * size_t.sizeof);
ndx2[i] = ndx1[n];
ndx2 = (ptr2 == null) ? new size_t[len] : ptr2[0 .. len];
n += fmax;
}
if (n >= len) {
{
m++;
size_t n, m;
n = m;
foreach (size_t i; 0 .. len) {
ndx2[i] = ndx1[n];
⚫
n += fmax;
if (n >= len) {
m++;
n = m;
}
}
}
}
}

// how long can our cyclic groups be?
// how long can our cyclic groups be?
immutable size_t grp = 1 + (len - 1) / fmax;
immutable size_t grp = 1 + (len - 1) / fmax;

// how many of them are full length?
// how many of them are full length?
immutable size_t lng = 1 + (len - 1) % fmax;
immutable size_t lng = 1 + (len - 1) % fmax;

// rotate each group
// rotate each group
{
⚫
for (size_t i = 0, j = 0; i < fmax; i++) {
immutable size_t first = ndx2[j];
size_t j;
immutable size_t glen = grp - (i < lng ? 0 : 1);
foreach (size_t i; 0 .. fmax) {
foreach (size_t k; 1 .. glen)
immutable size_t first = ndx2[j];
ndx1[j + k - 1] = ndx2[j + k];
immutable size_t glen = grp - (i < lng ? 0 : 1);
ndx1[j + glen - 1] = first;
foreach (size_t k; 1 .. glen)
j += glen;
ndx1[j + k - 1] = ndx2[j + k];
ndx1[j + glen - 1] = first;
j += glen;
}
}
}

// result is original permuted according to our cyclic groups
// result is original permuted according to our cyclic groups
foreach (size_t i; 0 .. len)
foreach (size_t i; 0 .. len)
result[ndx2[i]] = txt[ndx1[i]];
result[ndx2[i]] = txt[ndx1[i]];
}
}

void main() {
void main() {
auto data = ["abracadabra", "seesaw", "elk", "grrrrrr",
auto data = ["abracadabra", "seesaw", "elk", "grrrrrr",
"up", "a", "aabbbbaa", "", "xxxxx"];
"up", "a", "aabbbbaa", "", "xxxxx"];
foreach (txt; data) {
foreach (txt; data) {
auto shuf = txt.dup;
auto result = txt.dup;
bestShuffle(txt, shuf);
bestShuffle(txt, result);
immutable nequal = count!q{a[0] == a[1]}(zip(txt, shuf));
immutable nEqual = zip(txt, result).count!q{a[0] == a[1]}();
writefln("%s, %s, (%d)", txt, shuf, nequal);
writefln("%s, %s, (%d)", txt, result, nEqual);
}
}
}</lang>
}</lang>
{{out}}

Output:
<pre>abracadabra, brabacadaar, (0)
<pre>abracadabra, brabacadaar, (0)
seesaw, wssaee, (0)
seesaw, wssaee, (0)
Retrieved from "https://rosettacode.org/wiki/Best_shuffle"