Anonymous user
Best shuffle: Difference between revisions
Better first D version
(Better first D version) |
|||
Line 267:
=={{header|D}}==
{{
<lang d>import std.stdio, core.stdc.stdlib;
char[] bestShuffle(in char[] txt) {
int len = txt.length;
int mx = 0; // max char frequency
int[char.max+1] counts;
int j, n, m, k;
// how many of each character?
foreach (char c; txt) {
counts[c]++;
if (mx < counts[c])
mx = counts[c];
}
// all character positions, grouped by character
int[] ndx1 = (cast(int*)alloca(len * int.sizeof))[0 .. len];
ndx1[] = 0;
int i = 0;
foreach (ch; 0 .. counts.length)
if (counts[ch])
for (j = 0; j < len; j++)
if (ch == txt[j])
ndx1[i++]= j;
int[] ndx2 = (cast(int*)alloca(len * int.sizeof))[0 .. len];
for (i = 0, n = 0, m = 0; i < len; i++) {
ndx2[i] = ndx1[n];
n += mx;
if (
}
// how long can our cyclic groups be?
// how many of them are full length?
int lng = 1 + (len - 1) % mx;
// rotate each group
ndx1[] = 0;
for (i = 0, j = 0; i < mx; i++) {
int first = ndx2[j];
int glen = grp - (i < lng ? 0 : 1);
for (k = 1; k < glen; k++)
ndx1[j + k - 1] = ndx2[j + k];
ndx1[j + k - 1] = first;
j += glen;
}
// result is original permuted according to our cyclic groups
char[] result = new char[len];
foreach (ii; 0 .. len)
result[ndx2[ii]] = txt[ndx1[ii]];
return result;
}
void display(in char[] txt1, in char[] txt2) {
assert(txt1.length == txt2.length);
int score = 0;
foreach (i, c; txt1)
if (c == txt2[i])
score++;
writefln("%s, %s, (%d)", txt1, txt2, score);
}
void main() {
"grrrrrr", "up", "a", "aabbbbaa"];
foreach (txt; data)
}</lang>
Output:
<pre>abracadabra, brabacadaar, (0)
seesaw, wssaee, (0)
elk, kel, (0)
grrrrrr, rrrrrrg, (5)
up, pu, (0)
a, a, (1)
aabbbbaa, bbaaaabb, (0)</pre>
Using idea from [http://rosettacode.org/wiki/Talk:Best_shuffle#J_implementation_notes J implementation notes] at discussion page.
{{works with|D|2.051}}
|