Anonymous user
Best shuffle: Difference between revisions
m
→{{header|D}}: add cyclic group version
m (→{{header|C}}) |
m (→{{header|D}}: add cyclic group version) |
||
Line 153:
assert(bestShuffle("up".dup) == 0);
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>
| |||