Best shuffle: Difference between revisions

Content added Content deleted
(Cleaned C version)
(Improved first D version)
Line 282: Line 282:
=={{header|D}}==
=={{header|D}}==
{{trans|C}}
{{trans|C}}
<lang d>import std.stdio, core.stdc.stdlib;
<lang d>import std.stdio: writefln;


extern(C) pure nothrow void* alloca(size_t size);
⚫
char[] bestShuffle(in char[] txt) {

⚫
int len = txt.length;
⚫
pure nothrow void bestShuffle(in char[] txt, char[] result) {
int mx = 0; // max char frequency
int[char.max+1] counts;
enum int NCHAR = 256;
int j, n, m, k;
const int len = txt.length;

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


// how many of each character?
// how many of each character?
int[NCHAR] counts;
⚫
int fmax = 0;
foreach (char c; txt) {
foreach (char c; txt) {
counts[c]++;
counts[c]++;
if (mx < counts[c])
if (fmax < counts[c])
mx = counts[c];
fmax = counts[c];
}
}

⚫
// how long can our cyclic groups be?
⚫
const int grp = 1 + (len - 1) / fmax;

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


// all character positions, grouped by character
// all character positions, grouped by character
int[] ndx1 = (cast(int*)alloca(len * int.sizeof))[0 .. len];
int[] ndx1 = (cast(int*)alloca(len * int.sizeof))[0 .. len];
int i = 0;
for (int ch = 0, i = 0; ch < NCHAR; ch++)
foreach (ch; 0 .. counts.length)
if (counts[ch])
if (counts[ch])
foreach (j; 0 .. len)
for (j = 0; j < len; j++)
if (ch == txt[j]) {
if (ch == txt[j])
ndx1[i] = j;
ndx1[i++] = j;
i++;
}


// regroup them for cycles
// regroup them for cycles
int[] ndx2 = (cast(int*)alloca(len * int.sizeof))[0 .. len];
int[] ndx2 = (cast(int*)alloca(len * int.sizeof))[0 .. len];
for (i = 0, n = 0, m = 0; i < len; i++) {
for (int i = 0, n = 0, m = 0; i < len; i++) {
ndx2[i] = ndx1[n];
ndx2[i] = ndx1[n];
n += mx;
n += fmax;
if (n >= len)
if (n >= len) {
n = ++m;
m++;
n = m;
}
}
}

⚫
// how long can our cyclic groups be?
⚫
int grp = 1 + (len - 1) / mx;

⚫
// how many of them are full length?
⚫
int lng = 1 + (len - 1) % mx;


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


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


void display(in char[] txt1, in char[] txt2) {
void display(in char[] txt1, in char[] txt2)
in {
assert(txt1.length == txt2.length);
assert(txt1.length == txt2.length);
} body {
int score = 0;
int score = 0;
foreach (i, c; txt1)
foreach (i, c; txt1)
Line 350: Line 360:
auto data = ["abracadabra", "seesaw", "elk",
auto data = ["abracadabra", "seesaw", "elk",
"grrrrrr", "up", "a", "aabbbbaa"];
"grrrrrr", "up", "a", "aabbbbaa"];
foreach (txt; data)
foreach (txt; data) {
display(txt, bestShuffle(txt.dup));
int l = txt.length;
auto shuf = (cast(char*)alloca(l * char.sizeof))[0 .. l];
bestShuffle(txt, shuf);
display(txt, shuf);
}
}</lang>
}</lang>
Output:
Output:
Retrieved from "https://rosettacode.org/wiki/Best_shuffle"