|
=={{header|D}}==
<lang d>import std.stdio, std.random, std.algorithm, std.array;
{{trans|C}}
<lang d>import std.stdio, std.algorithm, std.range;
int bestShuffle(in dchar[] s1) {
extern(C) pure nothrow void* alloca(in size_t size);
int countSamePositions(in dchar[] r1, dchar[] r2, int len) {
int count;
for (int i; i < len; i++) {
if (r2[i] != '-' && r1[i] == r2[i]) {
count++;
}
}
return count;
}
const len = s1.length;
pure nothrow void bestShuffle(in char[] txt, char[] result) {
dchar[] s2 = s1.dup;
enum size_t NCHAR = cast(size_t)char.max + 1;
enum size_t MAX_VLA_SIZE = 1024;
immutable size_t len = txt.length;
if (len == 0)
return;
if (len < 3) {
// txt and result must have the same length
// allocate only when necessarys2.reverse;
if} (result.lengthelse != len){
result.length = len;
auto problemChar = sort!("a[1] > b[1]")(array(group(s2)))[0];
// how many of each character?
if ((problemChar[1] - len / 2) > 0) {
size_t[NCHAR] counts;
int numToRemove = problemChar[1] - (len - problemChar[1]);
size_t fmax = 0;
for (int i, j; i < len && j < numToRemove; i++) {
foreach (char c; txt) {
counts if (s2[ci]++; == problemChar[0]) {
if (fmax < counts s2[ci]) = '-';
fmax = counts[c] j++;
}
assert(fmax > 0 && fmax <= len);
// all character positions, grouped by character
size_t* ptr1 = null;
if ((len * size_t.sizeof) < MAX_VLA_SIZE)
ptr1 = cast(size_t*)alloca(len * size_t.sizeof);
size_t[] ndx1 = (ptr1 == null) ? new size_t[len] : ptr1[0..len];
for (size_t ch = 0, i = 0; ch < NCHAR; ch++)
if (counts[ch])
foreach (size_t j, char c; txt)
if (c == ch) {
ndx1[i] = j;
i++;
}
}
// regroup them for cycles
size_t* ptr2 = null;
if ((len * size_t.sizeof) < MAX_VLA_SIZE)
ptr2 = cast(size_t*)alloca(len * size_t.sizeof);
size_t[] ndx2 = (ptr2 == null) ? new size_t[len] : ptr2[0..len];
for (size_t i = 0, n = 0, m = 0; i < len; i++) {
ndx2[i] = ndx1[n];
n += fmax;
if (n >= len) {
m++;
n = m;
}
}
// how long can ourdo cyclic groups be?{
immutable size_t grp = 1 + for (int i = len; -i > 1; i--) / fmax;{
swap(s2[i-1], s2[uniform(0, i)]);
}
} while(countSamePositions(s1, s2, len) > 0);
// how many of themfor are(int fulli; length?i < len; i++) {
immutable size_t lng = 1 + if (lens2[i] -== 1'-') % fmax;{
s2[i] = problemChar[0];
// rotate each group }
}
for (size_t i = 0, j = 0; i < fmax; i++) {
immutable size_t first = ndx2[j];
immutable size_t glen = grp - (i < lng ? 0 : 1);
foreach (size_t k; 1 .. glen)
ndx1[j + k - 1] = ndx2[j + k];
ndx1[j + glen - 1] = first;
j += glen;
}
int samePos = countSamePositions(s1, s2, len);
// result is original permuted according to our cyclic groups
foreach writefln(size_t"%s i;%s 0(%s)", ..s1, lens2, samePos);
result[ndx2[i]] = txt[ndx1[i]];
return samePos;
}
unittest {
void main() {
assert(bestShuffle("immediately"d.dup) == 0);
auto data = ["abracadabra", "seesaw", "elk", "grrrrrr",
assert(bestShuffle("seesaw"d.dup) == 0);
"up", "a", "aabbbbaa", "", "xxxxx"];
assert(bestShuffle("abracadabra"d.dup) == 0);
foreach (txt; data) {
assert(bestShuffle("elk"d.dup) == 0);
auto shuf = txt.dup;
assert(bestShuffle(txt,"a"d.dup) == shuf1);
assert(bestShuffle("grrrrrr"d.dup) == 5);
immutable nequal = count!q{a[0] == a[1]}(zip(txt, shuf));
writefln("%s, %s, (%d)", txt, shuf, nequal);
}
}</lang>
Output:
<pre>abracadabra, brabacadaar, (0)
seesaw, wssaee, (0)
elk, kel, (0)
grrrrrr, rrrrrrg, (5)
up, pu, (0)
a, a, (1)
aabbbbaa, bbaaaabb, (0)
, , (0)
xxxxx, xxxxx, (5)</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}}
<lang d>import std.stdio, std.string, std.conv, std.algorithm, std.range, std.random ;
string shuffle(const string txt, bool bRandom = true) {
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
auto cut = (bRandom && g.length > 1) ? uniform(1, g.length) : 1 ;
g = (g[cut..$] ~ g[0..cut]) ;
}
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", "seesaw", "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)))) ;
auto r ="11-22-333-44-55" ;
writeln(r) ;
foreach(loop;0..4)
writefln("%s (%d)",
shuffle(r), count!"a[0]==a[1]"(zip(r,shuffle(r)))) ;
}</lang>
part of output:
<pre>11-22-333-44-55
-354431223--51- (0)
--34-35242-3511 (0)
--34435223--511 (0)
-354431223--51- (0)</pre>
=={{header|Haskell}}==
|