Jump to content

Best shuffle: Difference between revisions

Best shuffle (view source)

Revision as of 12:13, 21 April 2011

578 bytes added ,  13 years ago
Better first D version
(Better first D version)
Line 267:
 
=={{header|D}}==
{{works withtrans|D|2C}}
<lang d>import std.stdio, core.stdc.stdlib;
<lang d>int bestShuffle(dchar[] s1) {
 
char[] bestShuffle(in char[] txt) {
int countSamePositions(dchar[] r1, dchar[] r2) {
int len = txt.length;
return count!("a[0] == a[1] && a[1] != b")(zip(r1, r2), '-');
int mx = 0; // max char frequency
int[char.max+1] counts;
int j, n, m, k;
 
// how many of each character?
foreach (char c; txt) {
counts[c]++;
if (mx < counts[c])
mx = counts[c];
}
 
// all character positions, grouped by character
const len = s1.length;
int[] ndx1 = (cast(int*)alloca(len * int.sizeof))[0 .. len];
dchar[] s2 = s1.dup;
ndx1[] = 0;
int i = 0;
foreach (ch; 0 .. counts.length)
if (counts[ch])
for (j = 0; j < len; j++)
if (ch == txt[j])
ndx1[i++]= j;
 
if// (lenregroup <them 3)for {cycles
int[] ndx2 = (cast(int*)alloca(len * int.sizeof))[0 .. len];
s2.reverse;
}ndx2[] else= {0;
for (i = 0, n = 0, m = 0; i < len; i++) {
s2.sort;
ndx2[i] = ndx1[n];
 
n += mx;
auto problemChar = sort!("a[1] > b[1]")(array(group(s2)))[0];
if ((problemChar[1]n ->= len / 2) > 0) {
int numToRemoven = problemChar[1] - (len - problemChar[1])++m;
for (int i, j; i < len && j < numToRemove; i++) {
if (s2[i] == problemChar[0]) {
s2[i] = '-';
j++;
}
}
}
do {
for (int i = len; i > 1; i--) {
swap(s2[i-1], s2[uniform(0, i)]);
}
} while(countSamePositions(s1, s2) > 0);
for (int i; i < len; i++) {
if (s2[i] == '-') {
s2[i] = problemChar[0];
}
}
}
 
// how long can our cyclic groups be?
int samePos = countSamePositions(s1, s2);
writefln("%sint %sgrp (%s)",= s1,1 s2,+ samePos(len - 1) / mx;
 
// how many of them are full length?
return samePos;
int lng = 1 + (len - 1) % mx;
}</lang>
 
// rotate each group
ndx1[] = 0;
for (i = 0, j = 0; i < mx; i++) {
int first = ndx2[j];
int glen = grp - (i < lng ? 0 : 1);
for (k = 1; k < glen; k++)
ndx1[j + k - 1] = ndx2[j + k];
ndx1[j + k - 1] = first;
j += glen;
}
 
// result is original permuted according to our cyclic groups
char[] result = new char[len];
foreach (ii; 0 .. len)
result[ndx2[ii]] = txt[ndx1[ii]];
return result;
}
 
void display(in char[] txt1, in char[] txt2) {
output:<pre>abracadabra caararbdaab (0)
assert(txt1.length == txt2.length);
seesaw essawe (0)
int score = 0;
elk lke (0)
foreach (i, c; txt1)
grrrrrr rrrrrgr (5)
if (c == txt2[i])
up pu (0)
score++;
a a (1)
writefln("%s, %s, (%d)", txt1, txt2, score);
</pre>
}
 
void main() {
<lang d>unittest {
assert(bestShuffle(auto data = ["abracadabra".dup), =="seesaw", 0);"elk",
"grrrrrr", "up", "a", "aabbbbaa"];
assert(bestShuffle("seesaw".dup) == 0);
foreach (txt; data)
assert(bestShuffle("elk".dup) == 0);
assert display(txt, bestShuffle("grrrrrr"txt.dup) == 5);
assert(bestShuffle("up".dup) == 0);
assert(bestShuffle("a".dup) == 1);
}</lang>
Output:
<pre>abracadabra, brabacadaar, (0)
seesaw, wssaee, (0)
elk, kel, (0)
grrrrrr, rrrrrrg, (5)
up, pu, (0)
a, a, (1)
aabbbbaa, bbaaaabb, (0)</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}}
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/166844"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information