Best shuffle: Difference between revisions
Content added Content deleted
Line 1,152: | Line 1,152: | ||
// Assume alloca to be pure. |
// Assume alloca to be pure. |
||
//extern(C) pure nothrow void* alloca(in size_t size); |
//extern(C) pure nothrow void* alloca(in size_t size); |
||
enum size_t NCHAR = |
enum size_t NCHAR = size_t(char.max + 1); |
||
enum size_t MAX_VLA_SIZE = 1024; |
enum size_t MAX_VLA_SIZE = 1024; |
||
immutable size_t len = txt.length; |
immutable size_t len = txt.length; |
||
Line 1,166: | Line 1,166: | ||
size_t[NCHAR] counts; |
size_t[NCHAR] counts; |
||
size_t fmax = 0; |
size_t fmax = 0; |
||
foreach (char c; txt) { |
foreach (immutable char c; txt) { |
||
counts[c]++; |
counts[c]++; |
||
if (fmax < counts[c]) |
if (fmax < counts[c]) |
||
Line 1,185: | Line 1,185: | ||
{ |
{ |
||
int pos = 0; |
int pos = 0; |
||
foreach (size_t ch; 0 .. NCHAR) |
foreach (immutable size_t ch; 0 .. NCHAR) |
||
if (counts[ch]) |
if (counts[ch]) |
||
foreach (j, char c; txt) |
foreach (j, char c; txt) |
||
Line 1,204: | Line 1,204: | ||
{ |
{ |
||
size_t n, m; |
size_t n, m; |
||
foreach (size_t i; 0 .. len) { |
foreach (immutable size_t i; 0 .. len) { |
||
ndx2[i] = ndx1[n]; |
ndx2[i] = ndx1[n]; |
||
n += fmax; |
n += fmax; |
||
Line 1,214: | Line 1,214: | ||
} |
} |
||
// |
// 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? |
||
immutable size_t lng = 1 + (len - 1) % fmax; |
immutable size_t lng = 1 + (len - 1) % fmax; |
||
// |
// Rotate each group. |
||
{ |
{ |
||
size_t j; |
size_t j; |
||
foreach (size_t i; 0 .. fmax) { |
foreach (immutable size_t i; 0 .. fmax) { |
||
immutable size_t first = ndx2[j]; |
immutable size_t first = ndx2[j]; |
||
immutable size_t glen = grp - (i < lng ? 0 : 1); |
immutable size_t glen = grp - (i < lng ? 0 : 1); |
||
foreach (size_t k; 1 .. glen) |
foreach (immutable size_t k; 1 .. glen) |
||
ndx1[j + k - 1] = ndx2[j + k]; |
ndx1[j + k - 1] = ndx2[j + k]; |
||
ndx1[j + glen - 1] = first; |
ndx1[j + glen - 1] = first; |
||
Line 1,233: | Line 1,233: | ||
} |
} |
||
// |
// Result is original permuted according to our cyclic groups. |
||
foreach (size_t i; 0 .. len) |
foreach (immutable size_t i; 0 .. len) |
||
result[ndx2[i]] = txt[ndx1[i]]; |
result[ndx2[i]] = txt[ndx1[i]]; |
||
} |
} |
||
Line 1,244: | Line 1,244: | ||
auto result = txt.dup; |
auto result = txt.dup; |
||
bestShuffle(txt, result); |
bestShuffle(txt, result); |
||
immutable nEqual = zip(txt, result).count!q{a[0] == a[1]} |
immutable nEqual = zip(txt, result).count!q{ a[0] == a[1] }; |
||
writefln("%s, %s, (%d)", txt, result, nEqual); |
writefln("%s, %s, (%d)", txt, result, nEqual); |
||
} |
} |