Best shuffle: Difference between revisions
Content added Content deleted
m (→{{header|C}}) |
m (→{{header|D}}: add cyclic group version) |
||
Line 153: | Line 153: | ||
assert(bestShuffle("up".dup) == 0); |
assert(bestShuffle("up".dup) == 0); |
||
assert(bestShuffle("a".dup) == 1); |
assert(bestShuffle("a".dup) == 1); |
||
}</lang> |
|||
Using idea from [http://rosettacode.org/wiki/Talk:Best_shuffle#J_implementation_notes J implementation notes] at discussion page. |
|||
{{works with|D|2.051}} |
|||
<lang d>import std.stdio, std.string, std.conv, std.algorithm, std.range ; |
|||
string shuffle(const string txt) { |
|||
if(txt.length <= 3) return text(txt[1..$] ~ txt[0]) ; |
|||
auto s = dtext(txt) ; |
|||
int[][dchar] gpChar ; |
|||
foreach(i, dc ; s) gpChar[dc] ~= i ; |
|||
auto gpIdx = gpChar.values ; |
|||
sort!"a.length > b.length"(gpIdx) ;// make sure largest group come first |
|||
auto maxGpLen = gpIdx[0].length ; |
|||
auto gpCyc = new int[][](maxGpLen); |
|||
auto idx = 0 ; |
|||
foreach(ix ; reduce!"a ~ b"(gpIdx))// regroup for cycles |
|||
gpCyc[idx++ % maxGpLen] ~= ix ; |
|||
auto raw = reduce!"a ~ b"(gpCyc) ; // get original idx order |
|||
foreach(ref g;gpCyc) // cycling within group |
|||
g = (g[1..$] ~ g[0]) ; |
|||
auto cyc = reduce!"a ~ b"(gpCyc) ; // get cyclic idx order |
|||
auto r = new dchar[](s.length) ; // make shuffled string |
|||
foreach(ix;0..s.length) |
|||
r[raw[ix]] = s[cyc[ix]] ; |
|||
return text(r) ; |
|||
} |
|||
void main() { |
|||
auto txt = ["abracadabra", "eesaw", "elk", "grrrrrr", "up", "a"] ; |
|||
auto fmx = format("%%%ds", reduce!max(map!"a.length"(txt))) ; |
|||
foreach(t;txt) |
|||
writefln(fmx ~" -> "~fmx~" (%d)", |
|||
t, shuffle(t), count!"a[0]==a[1]"(zip(t,shuffle(t)))) ; |
|||
}</lang> |
}</lang> |
||