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 |
<lang d>import std.stdio: writefln; |
||
extern(C) pure nothrow void* alloca(size_t size); |
|||
⚫ | |||
⚫ | |||
⚫ | |||
int mx = 0; // max char frequency |
|||
int |
enum int NCHAR = 256; |
||
const int len = txt.length; |
|||
// txt and result must have the same length |
|||
// allocate only when necessary |
|||
if (result.length != len) |
|||
⚫ | |||
// how many of each character? |
// how many of each character? |
||
int[NCHAR] counts; |
|||
⚫ | |||
foreach (char c; txt) { |
foreach (char c; txt) { |
||
counts[c]++; |
counts[c]++; |
||
if ( |
if (fmax < counts[c]) |
||
fmax = counts[c]; |
|||
} |
} |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
// 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++) |
||
if (counts[ch]) |
|||
foreach (j; 0 .. len) |
|||
if (ch == txt[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 += |
n += fmax; |
||
if (n >= len) |
if (n >= len) { |
||
m++; |
|||
n = m; |
|||
} |
|||
} |
} |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
// rotate each group |
// rotate each group |
||
for (i = 0, j = 0; 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); |
||
foreach (k; 1 .. glen) |
|||
ndx1[j + k - 1] = ndx2[j + k]; |
ndx1[j + k - 1] = ndx2[j + k]; |
||
ndx1[j + |
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 |
||
foreach (i; 0 .. len) |
|||
result[ndx2[i]] = txt[ndx1[i]]; |
|||
foreach (ii; 0 .. len) |
|||
⚫ | |||
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) { |
||
int l = txt.length; |
|||
auto shuf = (cast(char*)alloca(l * char.sizeof))[0 .. l]; |
|||
bestShuffle(txt, shuf); |
|||
display(txt, shuf); |
|||
} |
|||
}</lang> |
}</lang> |
||
Output: |
Output: |