Best shuffle: Difference between revisions

{{trans|Perl 6Icon}}

TheIf equivalent programs for [[#Perl 6|Perl 6]] and for [[#Ruby|Ruby]] use severalthose built-in array functions. But if those array functions seem strange to you, and if you can understand this bunch ofthese for loops, then you might prefer this Awk program. This algorithm counts the letters in the string, sorts the positions, and fills the positions in order.

<langsyntaxhighlight lang="awk"># out["string"] = best shuffle of string _s_

# if we can avoid matching characteerscharacters that way.

}</langsyntaxhighlight>

<langsyntaxhighlight lang="bash">$ awk -f best-shuffle.awk

a, a, (1)</langsyntaxhighlight>

The output might change if the <tt>for (c in set)</tt> loop iterates the array in a different order. (Awk specifies not an order of iteration.)

In essence: we form cyclic groups of character indices where each cyclic group is guaranteed to represent each character only once (two instances of the letter 'a' must have their indices in separate groups), and then we rotate each of the cyclic groups. We then use the before/after version of these cycles to shuffle the original text. The only way a character can be repeated, here, is when a cyclic group contains only one character index, and this can only happen when more than half of the text uses that character. This is C99 code.

<langsyntaxhighlight lang="c">#include <stdlib.h>

void best_shuffle(const unsigned char* txt, unsigned char* result) {

const intsize_t ncharlen = 256strlen(txt);

const intif (len == (int)strlen((char*)txt0);

assert(len == (int)strlen((char*)result));

intsize_t counts[ncharUCHAR_MAX];

memset(counts, '\0', ncharUCHAR_MAX * sizeof(int));

intsize_t fmax = 0;

for (intsize_t i = 0; i < len; i++) {

counts[(unsigned char)txt[i]]++;

const intsize_t fnew = counts[(unsigned char)txt[i]];

intsize_t *ndx1[ = malloc(len] * sizeof(size_t));

forif (int chndx1 = 0, i = 0; ch < nchar; ch++NULL)

for (intsize_t j = 0; j < len; j++)

if (ch == (unsigned char)txt[j]) {

ndx1[i++] = j;

intsize_t *ndx2[ = malloc(len] * sizeof(size_t));

forif (int indx2 = 0, n = 0, m = 0; i < len; i++NULL) {

if (n >= len) {

n = m++m;

for (intsize_t i = 0, j = 0; i < fmax; i++) {

intconst size_t first = ndx2[j];

intconst size_t glen = grp - (i < lng ? 0 : 1);

for (intsize_t k = 1; k < glen; k++)

for (intsize_t i = 0; i < len; i++)

void display(const char* txt1, const char* txt2) {

intconst size_t len = (int)strlen(txt1);

for (intsize_t i = 0; i < len; i++)

(void)printf("%s, %s, (%du)\n", txt1, txt2, score);

const char* data[] = {"abracadabra", "seesaw", "elk", "grrrrrr",

"up", "a", "aabbbbaa", "", "xxxxx"};

const intsize_t data_len = sizeof(data) / sizeof(data[0]);

for (intsize_t i = 0; i < data_len; i++) {

const intsize_t shuf_len = (int)strlen(data[i]) + 1;

unsigned char shuf[shuf_len];

memset(shuf, 0xFF, shuf_len * sizeof(unsigned char)shuf);

best_shuffle((unsigned char*)data[i], shuf);

display(data[i], (char*)shuf);

}</langsyntaxhighlight>

aabbbbaa, bbaaaabb, (0)</pre>

<langsyntaxhighlight Clojurelang="clojure">(defn score [before after]

["a" "a" 1]]</langsyntaxhighlight>

extern(C) pure nothrow void* alloca(in size_t size);

pure nothrow void bestShuffle(in char[] txt, ref char[] result) pure nothrow {

enum// intAssume NCHARalloca =to 256;be pure.

intsize_t[NCHAR] counts;

intsize_t fmax = 0;

foreach (immutable char c; txt) {

if (counts[ch])size_t* ptr1;

foreachif (j;(len 0* size_t..sizeof) len< MAX_VLA_SIZE)

ptr1 = if cast(chsize_t*)alloca(len ==* txt[j]size_t.sizeof) {;

// If alloca() has failed, or the memory needed is too ndx1[i] = j;much

// large, then allocate from the i++;heap.

ndx1 = (ptr1 == null) ? new size_t[len] }: ptr1[0 .. len];

ndx2[i]size_t* = ndx1[n]ptr2;

nif +=((len fmax;* size_t.sizeof) < MAX_VLA_SIZE)

if (n > ptr2 = lencast(size_t*)alloca(len {* size_t.sizeof);

n = m;}

// rotateHow eachlong groupcan our cyclic groups be?

forimmutable (intsize_t igrp = 0,1 j+ =(len 0;- i1) </ fmax; i++) {

immutable size_t lng = foreach1 + (k;len - 1) ..% glen)fmax;

j += glen;{

// resultResult is original permuted according to our cyclic groups.

foreach (immutable size_t i; 0 .. len)

auto data = ["abracadabra", "seesaw", "elk", "grrrrrr",

"grrrrrrup", "upa", "aaabbbbaa", "aabbbbaa", "xxxxx"];

intauto lresult = txt.lengthdup;

bestShuffleimmutable nEqual = zip(txt, shufresult).count!q{ a[0] == a[1] };

displaywritefln("%s, %s, (%d)", txt, shufresult, nEqual);

}</langsyntaxhighlight>

aabbbbaa, bbaaaabb, (0)</pre>

return text(r)original: string;

where positions test s = do

putStrLn $ map (map fst)unwords $ groupBy[ ((==)show `on` snd) $s

sortBy (compare `on` snd) $ zip [0..] s , show x

<lang haskell>bestShuffleshuffle :: Eq a => [a] -> [a]

Additionally, this can be trivially modified to randomize the shuffle. by uncommenting the line

end</langsyntaxhighlight>

Based on [http://rosettacode.org/mw/index.php?title=Best_shuffle&oldid=97419#J Dan Bron's approach]:

<langsyntaxhighlight lang="j">bestShuf =: verb define

yy=. <@(\:{~ ?~@#&>)@:(<@I.@=) y

y C.~ (;yy) </.~ (i.#y) |~ #>{./#@> yy

<langsyntaxhighlight lang="j"> fmtBest&>;:'abracadabra seesaw elk grrrrrr up a'

abracadabra, bdabararaacbdacararaab (0)

grrrrrr, rgrrrrrrrrrrrg (5)

a, a (1) </syntaxhighlight>

<langsyntaxhighlight lang="javascript">function raze(a) { // like .join('') except producing an array instead of a string

var r= [];

for (var j= 0; j<a.length; j++)

for (var k= 0; k<a[j].length; k++) r.push(a[j][k]);

return r;

var chs= txt.split('');

var gr= {};

var mx= 0;

for (var j= 0; j<chs.length; j++) {

var ch= chs[j];

if (null == gr[ch]) gr[ch]= [];

gr[ch].push(j);

if (mx < gr[ch].length) mx++;

var inds= [];

for (var ch in gr) inds.push(shuffle(gr[ch]));

var ndx= raze(inds);

var cycles= [];

for (var k= 0; k < mx; k++) cycles[k]= [];

for (var j= 0; j<chs.length; j++) cycles[j%mx].push(ndx[j]);

var ref= raze(cycles);

for (var k= 0; k < mx; k++) cycles[k].push(cycles[k].shift());

var prm= raze(cycles);

var shf= [];

for (var j= 0; j<chs.length; j++) shf[ref[j]]= chs[prm[j]];

return shf.join('');

var r= bestShuf(ex);

var n= 0;

for (var j= 0; j<ex.length; j++)

n+= ex.substr(j, 1) == r.substr(j,1) ?1 :0;

return ex+', '+r+', ('+n+')';

}</langsyntaxhighlight>

<langsyntaxhighlight lang="html"><html><head><title></title></head><body><pre id="out"></pre></body></html>

</script></langsyntaxhighlight>

grrrrrr, rrrrrrgrgrrrrr, (5)

a, a, (1))</lang>

{ best = x

my %posrankb = classify { @orig[$^i] }, keys @orig;-2

myfor @k = map *.key(c, sortrankc) *.value.elems,in %pos;cnt

for# @k(Save ->characters $letterwith {less supply.)

# Avoid identical %pos{$letter} or next;characters.

if c == x; pushrankc @pos,= %pos{$letter}.pop;-1 end

if rankc > %pos{$letter}.elems or %pos.delete: $letter;rankb

} best = c

my @new = Any xxvar count = $s.chars;0

# in @pos, but skip ahead in @letters if we(s1[i] can== avoidthis[i]) count++

<langsyntaxhighlight PicoLisplang="picolisp">(de bestShuffle (Str)

(prinl Str " " Res " (" (cnt = Str Res) ")") ) ) )</langsyntaxhighlight>

end shuffle;</syntaxhighlight>

</langpre>

<langsyntaxhighlight Prologlang="prolog">:- dynamic score/2.