Anonymous user
Best shuffle: Difference between revisions
→Deterministic approach
Line 1,152:
// Assume alloca to be pure.
//extern(C) pure nothrow void* alloca(in size_t size);
enum size_t NCHAR =
enum size_t MAX_VLA_SIZE = 1024;
immutable size_t len = txt.length;
Line 1,166:
size_t[NCHAR] counts;
size_t fmax = 0;
foreach (immutable char c; txt) {
counts[c]++;
if (fmax < counts[c])
Line 1,185:
{
int pos = 0;
foreach (immutable size_t ch; 0 .. NCHAR)
if (counts[ch])
foreach (j, char c; txt)
Line 1,204:
{
size_t n, m;
foreach (immutable size_t i; 0 .. len) {
ndx2[i] = ndx1[n];
n += fmax;
Line 1,214:
}
//
immutable size_t grp = 1 + (len - 1) / fmax;
//
immutable size_t lng = 1 + (len - 1) % fmax;
//
{
size_t j;
foreach (immutable size_t i; 0 .. fmax) {
immutable size_t first = ndx2[j];
immutable size_t glen = grp - (i < lng ? 0 : 1);
foreach (immutable size_t k; 1 .. glen)
ndx1[j + k - 1] = ndx2[j + k];
ndx1[j + glen - 1] = first;
Line 1,233:
}
//
foreach (immutable size_t i; 0 .. len)
result[ndx2[i]] = txt[ndx1[i]];
}
Line 1,244:
auto result = txt.dup;
bestShuffle(txt, result);
immutable nEqual = zip(txt, result).count!q{ a[0] == a[1] }
writefln("%s, %s, (%d)", txt, result, nEqual);
}
| |||