103 lines
3 KiB
D
103 lines
3 KiB
D
import std.stdio, std.algorithm, std.range;
|
|
|
|
extern(C) pure nothrow void* alloca(in size_t size);
|
|
|
|
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 = size_t(char.max + 1);
|
|
enum size_t MAX_VLA_SIZE = 1024;
|
|
immutable size_t len = txt.length;
|
|
if (len == 0)
|
|
return;
|
|
|
|
// txt and result must have the same length
|
|
// allocate only when necessary
|
|
if (result.length != len)
|
|
result.length = len;
|
|
|
|
// how many of each character?
|
|
size_t[NCHAR] counts;
|
|
size_t fmax = 0;
|
|
foreach (immutable char c; txt) {
|
|
counts[c]++;
|
|
if (fmax < counts[c])
|
|
fmax = counts[c];
|
|
}
|
|
assert(fmax > 0 && fmax <= len);
|
|
|
|
// all character positions, grouped by character
|
|
size_t[] ndx1;
|
|
{
|
|
size_t* ptr1;
|
|
if ((len * size_t.sizeof) < MAX_VLA_SIZE)
|
|
ptr1 = cast(size_t*)alloca(len * size_t.sizeof);
|
|
// If alloca() has failed, or the memory needed is too much
|
|
// large, then allocate from the heap.
|
|
ndx1 = (ptr1 == null) ? new size_t[len] : ptr1[0 .. len];
|
|
}
|
|
{
|
|
int pos = 0;
|
|
foreach (immutable size_t ch; 0 .. NCHAR)
|
|
if (counts[ch])
|
|
foreach (j, char c; txt)
|
|
if (c == ch) {
|
|
ndx1[pos] = j;
|
|
pos++;
|
|
}
|
|
}
|
|
|
|
// regroup them for cycles
|
|
size_t[] ndx2;
|
|
{
|
|
size_t* ptr2;
|
|
if ((len * size_t.sizeof) < MAX_VLA_SIZE)
|
|
ptr2 = cast(size_t*)alloca(len * size_t.sizeof);
|
|
ndx2 = (ptr2 == null) ? new size_t[len] : ptr2[0 .. len];
|
|
}
|
|
{
|
|
size_t n, m;
|
|
foreach (immutable size_t i; 0 .. len) {
|
|
ndx2[i] = ndx1[n];
|
|
n += fmax;
|
|
if (n >= len) {
|
|
m++;
|
|
n = m;
|
|
}
|
|
}
|
|
}
|
|
|
|
// How long can our cyclic groups be?
|
|
immutable size_t grp = 1 + (len - 1) / fmax;
|
|
|
|
// How many of them are full length?
|
|
immutable size_t lng = 1 + (len - 1) % fmax;
|
|
|
|
// Rotate each group.
|
|
{
|
|
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;
|
|
j += glen;
|
|
}
|
|
}
|
|
|
|
// Result is original permuted according to our cyclic groups.
|
|
foreach (immutable size_t i; 0 .. len)
|
|
result[ndx2[i]] = txt[ndx1[i]];
|
|
}
|
|
|
|
void main() {
|
|
auto data = ["abracadabra", "seesaw", "elk", "grrrrrr",
|
|
"up", "a", "aabbbbaa", "", "xxxxx"];
|
|
foreach (txt; data) {
|
|
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);
|
|
}
|
|
}
|