Best shuffle: Difference between revisions

Content added Content deleted
(Updates D entries, tags)
Line 1,051:
 
=={{header|D}}==
===Simpler Version===
{{works with|D|2}}
Translation of [[Best_shuffle#Icon_and_Unicon|Icon]] via [[Best_shuffle#AWK|AWK]]
<lang d>import std.stdio, std.random, std.algorithm, std.conv, std.range,
std.typecons;
 
auto bestShuffle(in dstring o) {
auto s = o.dup;
s.randomShuffle(s);
 
▼
foreach (i, ref ci; s) {
if (ci != o[i])
continue;
foreach (j, ref cj; s)
if (ci != cj && ci != o[j] && cj != o[i]) {
swap(ci, cj);
Line 1,070:
}
 
return tuple(s, zip(s, o).count!q{ a[0] == a[1] }(zip(s, o)));
} unittest {▼
}
 
▲unittest {
assert(bestShuffle("abracadabra"d)[1] == 0);
assert(bestShuffle("immediately"d)[1] == 0);
Line 1,084 ⟶ 1,082:
}
 
void main(/*in*/ string[] args) {
if (args.length > 1) {
string entry = join(args[1 .. $], .join(" ");
auto res = bestShuffle(to!dstring(entry.dtext().bestShuffle();
writefln("%s : %s (%sd)", entry, res[0], res[1].tupleof);
}
}</lang>
===AlternativeFaster versionVersion===
<lang d>import std.stdio, std.algorithm, std.range;
 
extern(C) pure nothrow void* alloca(in size_t size);
 
pure nothrow void bestShuffle(in char[] txt, ref char[] result) pure nothrow {
// Assume alloca to be pure.
//extern(C) pure nothrow void* alloca(in size_t size);
enum size_t NCHAR = cast(size_t)char.max + 1;
enum size_t MAX_VLA_SIZE = 1024;
Line 1,102:
if (len == 0)
return;
 
// txt and result must have the same length
// allocate only when necessary
if (result.length != len)
result.length = len;
 
// how many of each character?
size_t[NCHAR] counts;
Line 1,117:
}
assert(fmax > 0 && fmax <= len);
 
// all character positions, grouped by character
size_t*[] ptr1 = nullndx1;
▲ {
if ((len * size_t.sizeof) < MAX_VLA_SIZE)
ptr1 = cast(size_t*)alloca(len * size_t.sizeof)ptr1;
size_t[] ndx1 = (ptr1 ==if null)((len ? new* size_t[len].sizeof) :< ptr1[0..len];MAX_VLA_SIZE)
for (size_t ch = 0, i = 0; chptr1 <= NCHAR;cast(size_t*)alloca(len ch++* size_t.sizeof);
// If alloca() has failed, or the memory needed is too much
if (counts[ch])▼
// large, then allocate foreach (size_t j, charfrom c;the txt)heap.
ndx1 = (ptr1 == null) ? new size_t[len] if: (cptr1[0 == ch).. {len];
}
ndx1[i] = j;▼
{
i++;▼
int pos = }0;
foreach (size_t ch; 0 .. NCHAR)
▲ if (counts[ch])
foreach (j, char c; txt)
if (c == ch) {
▲ ndx1[ipos] = j;
pos++;
▲ i++;}
}
 
// regroup them for cycles
size_t*[] ptr2 = nullndx2;
{
if ((len * size_t.sizeof) < MAX_VLA_SIZE)
ptr2 = cast(size_t*)alloca(len * size_t.sizeof)ptr2;
size_t[] ndx2 = (ptr2 ==if null)((len ? new* size_t[len].sizeof) :< ptr2[0..len];MAX_VLA_SIZE)
for (size_t i = 0, n = 0, mptr2 = 0;cast(size_t*)alloca(len i* < lensize_t.sizeof); i++) {
ndx2 = (ptr2 == null) ? new size_t[ilen] =: ndx1ptr2[n0 .. len];
n += fmax;}
if (n >= len) {
size_t n, m++;
foreach (size_t i; 0 n.. =len) m;{
ndx2[i] = ndx1[n];
for (size_t i = 0, j = 0; in <+= fmax; i++) {▼
if (n >= len) {
m++;
n = m;
}
}
}
 
// how long can our cyclic groups be?
immutable size_t grp = 1 + (len - 1) / fmax;
 
// how many of them are full length?
immutable size_t lng = 1 + (len - 1) % fmax;
 
// rotate each group
{
▲ for (size_t i = 0, j = 0; i < fmax; i++) {
immutable size_t first = ndx2[j];
immutableforeach (size_t glen = grp - (i < lng ?; 0 :.. 1fmax); {
foreach (size_t k; 1 ..immutable glen)size_t first = ndx2[j];
ndx1[jimmutable +size_t kglen = grp - 1](i =< ndx2[jlng +? k]0 : 1);
ndx1[j + glen - 1]foreach =(size_t firstk; 1 .. glen)
ndx1[j + k - 1] = glenndx2[j + k];
ndx1[j + glen - 1] = first;
j += glen;
}
}
 
// result is original permuted according to our cyclic groups
foreach (size_t i; 0 .. len)
result[ndx2[i]] = txt[ndx1[i]];
}
 
void main() {
auto data = ["abracadabra", "seesaw", "elk", "grrrrrr",
"up", "a", "aabbbbaa", "", "xxxxx"];
foreach (txt; data) {
auto shufresult = txt.dup;
bestShuffle(txt, shufresult);
immutable nequalnEqual = zip(txt, result).count!q{a[0] == a[1]}(zip(txt, shuf));
writefln("%s, %s, (%d)", txt, shufresult, nequalnEqual);
}
}</lang>
{{out}}
 
Output:
<pre>abracadabra, brabacadaar, (0)
seesaw, wssaee, (0)
Retrieved from "https://rosettacode.org/wiki/Best_shuffle"