Best shuffle: Difference between revisions
Content added Content deleted
(→{{header|Javascript}}: sp) |
(→{{header|D}}: putting my own shuffle back, because it produces a different result everytime, which is what I had in mind when I created the task) |
||
Line 342: | Line 342: | ||
=={{header|D}}== |
=={{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 |
|||
s2.reverse; |
|||
} else { |
|||
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) { |
|||
if (s2[i] == problemChar[0]) { |
|||
s2[i] = '-'; |
|||
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; |
|||
} |
} |
||
} |
|||
do { |
|||
for (int i = len; i > 1; i--) { |
|||
swap(s2[i-1], s2[uniform(0, i)]); |
|||
} |
|||
} while(countSamePositions(s1, s2, len) > 0); |
|||
for (int i; i < len; i++) { |
|||
if (s2[i] == '-') { |
|||
s2[i] = problemChar[0]; |
|||
} |
|||
} |
|||
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 |
|||
writefln("%s %s (%s)", s1, s2, 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("a"d.dup) == 1); |
|||
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}}== |
=={{header|Haskell}}== |