Best shuffle: Difference between revisions

 

 

 

 

=={{header|Ada}}==

{{trans|AWK}}

 

procedure Best_Shuffle is

 

begin

for I in S'Range loop

for J in S'Range loop

end if;

end loop;

end Best_Shuffle;

 

 

begin -- main procedure

declare

begin

for I in Original'Range loop

end if;

end loop;

end;

end loop;

 

=={{header|AutoHotkey}}==

Loop Parse, Words,`,

out .= Score(A_LoopField, Shuffle(A_LoopField))

r++

return a ", " b ", (" r ")`n"

Output:

<pre>abracadabra, caadarrbaab, (0)

a, a, (1)

</pre>

=={{header|AWK}}==

The Icon and Unicon program uses a simple algorithm of swapping. This is relatively easy to translate to Awk.

 

scram = best_shuffle($0)

print $0 " -> " scram " (" unchanged($0, scram) ")"

}

return count

 

This program has the same output as the Icon and Unicon program.

 

 

* to sort an array,

If those built-in array functions seem strange to you, and if you can understand these 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.

 

# out["score"] = number of matching characters

function best_shuffle(out, s, c, i, j, k, klen, p, pos, set, rlen, slen) {

words[i], result["string"], result["score"]

}

 

Output:

 

abracadabra, baarrcadaab, (0)

seesaw, essewa, (0)

grrrrrr, rgrrrrr, (5)

up, pu, (0)

 

The output might change if the <tt>for (c in set)</tt> loop iterates the array in a different order.

 

=={{header|Bracmat}}==

Not optimized:

( shuffle

= m car cdr todo a z count string

)

& Done

 

Optimized (~100 x faster):

( shuffle

= m car cdr todo a z count M string tried

)

& Done

Output:

abracadabra (0.b a a r a c a d r a b)

seesaw (0.e s s e w a)

a (1.a)

{!} Done

=={{header|C}}==

 

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.

 

#include <stdio.h>

#include <string.h>

 

int main() {

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

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

 

#ifdef DEBUG

shuf[shuf_len - 1] = '\0';

#endif

 

return EXIT_SUCCESS;

Output:

<pre>abracadabra, brabacadaar, (0)

 

===Version with random result===

#include <stdlib.h>

#include <string.h>

* to generate permutations

*/

{

int i, c;

}

 

{

least_overlap = strlen(str);

do_string("");

return 0;

grrrrrr -> rrgrrrr, overlap 5

elk -> kel, overlap 0

seesaw -> ewsesa, overlap 0

 

=={{header|C sharp|C#}}==

For both solutions, a class is used to encapsulate the original string and to scrambling. A private function of the class does the actual sorting. An implicit conversion from string is also provided to allow for simple initialization, e.g.:

Which will immediately shuffle each word.

 

A sequential solution, which always produces the same output for the same input.

using System;

using System.Text;

}

}

 

And a randomized solution, which will produce a more or less different result on every run:

using System;

using System.Text;

}

}

 

A sample output for the sequential shuffle:

a, a, (1)

</pre>

 

=={{header|Clojure}}==

Uses same method as J

 

(->> (map = before after)

(filter true? ,)

["grrrrrr" "rgrrrrr" 5]

["up" "pu" 0]

=={{header|Common Lisp}}==

 

 

 

 

(defun best-shuffle (str)

(let ((c (all-best-shuffles str)))

(elt c (random (length c)))))

(format t "All best shuffles:")

(print (all-best-shuffles "seesaw"))

(dolist (s (list "abracadabra" "seesaw" "elk" "grrrrrr" "up" "a"))

 

up: (pu 0)

 

 

 

=={{header|D}}==

Translation of [[Best_shuffle#Icon_and_Unicon|Icon]] via [[Best_shuffle#AWK|AWK]]

auto s = o.dup;

if (ci != o[i])

continue;

if (ci != cj && ci != o[j] && cj != o[i]) {

swap(ci, cj);

}

 

}

 

if (args.length > 1) {

}

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

enum size_t MAX_VLA_SIZE = 1024;

immutable size_t len = txt.length;

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;

size_t fmax = 0;

counts[c]++;

if (fmax < counts[c])

}

assert(fmax > 0 && fmax <= len);

// all character positions, grouped by character

// regroup them for cycles

}

}

immutable size_t grp = 1 + (len - 1) / fmax;

immutable size_t lng = 1 + (len - 1) % fmax;

}

result[ndx2[i]] = txt[ndx1[i]];

}

void main() {

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

"up", "a", "aabbbbaa", "", "xxxxx"];

foreach (txt; data) {

}

<pre>abracadabra, brabacadaar, (0)

seesaw, wssaee, (0)

, , (0)

xxxxx, xxxxx, (5)</pre>

 

=={{header|Go}}==

{{trans|Icon and Unicon}}

 

import (

"fmt"

"time"

)

 

func main() {

for _, s := range ts {

// create shuffled byte array of original string

}

// algorithm of Icon solution

if i != j && t[i] != s[j] && t[j] != s[i] {

t[i], t[j] = t[j], t[i]

fmt.Printf("%s -> %s (%d)\n", s, string(t), count)

}

<pre>

abracadabra -> raaracbbaad (0)

a -> a (1)

</pre>

 

=={{header|Haskell}}==

 

 

 

 

 

 

 

 

 

=={{header|Icon}} and {{header|Unicon}}==

The approach taken requires 2n memory and will run in O(n^2) time swapping once per final changed character. The algorithm is concise and conceptually simple avoiding the lists of indices, sorting, cycles, groups, and special cases requiring rotation needed by many of the other solutions. It proceeds through the entire string swapping characters ensuring that neither of the two characters are swapped with another instance of themselves in the ''original'' string.

 

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

while scram := bestShuffle(line := read()) do

write(line," -> ",scram," (",unchanged(line,scram),")")

every (count := 0) +:= (s1[i := 1 to *s1] == s2[i], 1)

return count

 

The code works in both Icon and Unicon.

->

</pre>

=={{header|J}}==

 

 

yy=. <@({~ ?~@#)@I.@= y

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

y,', ',b,' (',')',~":+/b=y

)

 

yy is (a list of) boxes of (lists of) indices where all characters selected by indices in a box are the same, and where the first box is the biggest box (contains the most indices). The phrase <code>({~ ?~@#)</code> shuffles the indices going into each box which makes the (deterministic) rotate which follows produce differing results sometimes (but only when that is possible).

Example:

 

abracadabra, bdacararaab (0)

seesaw, eawess (0)

grrrrrr, rrrrrrg (5)

up, pu (0)

=={{header|Java}}==

Translation of [[Best_shuffle#Icon_and_Unicon|Icon]] via [[Best_shuffle#AWK|AWK]]

 

public class BestShuffle {

public static void main(String[] args) {

String[] words = {"abracadabra", "seesaw", "grrrrrr", "pop", "up", "a"};

public static String bestShuffle(final String s1) {

char[] s2 = s1.toCharArray();

for (int i = 0; i < s2.length; i++) {

for (int j = 0; j < s2.length; j++) {

if (s2[i] != s2[j] && s2[i] != s1.charAt(j) && s2[j] != s1.charAt(i)) {

}

return s1 + " " + new String(s2) + " (" + count(s1, s2) + ")";

}

 

private static int count(final String s1, final char[] s2) {

int count = 0;

return count;

}

 

Output:

up pu (0)

a a (1)</pre>

=={{header|JavaScript}}==

 

Based on the J implementation (and this would be a lot more concise if we used something like jQuery):

 

var r= [];

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

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

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

 

Example:

 

<script type="text/javascript">

/* ABOVE CODE GOES HERE */

for (var i= 0; i<sample.length; i++)

document.getElementById('out').innerHTML+= disp(sample[i])+'\r\n';

 

Produced:

seesaw, ewaess, (0)

elk, lke, (0)

grrrrrr, rrrrrgr, (5)

up, pu, (0)

 

=={{header|OCaml}}==

 

Deterministic

 

let len = String.length s in

let r = String.copy s in

test "up";

test "a";

 

Run:

'up', 'pu' -> 0

'a', 'a' -> 1</pre>

 

 

 

use Algorithm::Permute;

 

 

}

 

 

 

 

 

 

 

 

 

 

}

 

 

=={{header|PHP}}==

Translation of [[Best_shuffle#Icon_and_Unicon|Icon]] via [[Best_shuffle#AWK|AWK]]

echo bestShuffle($w) . '<br>';

 

$cnt++;

return "($cnt)";

 

Output:

up pu (0)

a a (1)</pre>

 

=={{header|PicoLisp}}==

(let Lst NIL

(for C (setq Str (chop Str))

(setq Lst (delete @ Lst)) ) )

Str )

Output:

<pre>: (bestShuffle "abracadabra")

: (bestShuffle "a")

a a (1)</pre>

=={{header|PL/I}}==

declare (s, saves) character (20) varying, c character (1);

declare t(length(s)) bit (1);

end search;

 

 

OUTPUT:

abracadabra

baaracadrab 0

A

A 1

=={{header|Prolog}}==

Works with SWI-Prolog

 

best_shuffle :-

run(Var,[Other|RRest], [1,Var],[Other|RRest]):-

dif(Var,Other).

 

output : <pre> ?- test.

a : a (1)

true .

</pre>

=={{header|PureBasic}}==

This solution creates cycles of letters of letters that are then rotated to produce the final maximal shuffle. It includes an extra sort step that ensures the original string to be returned if it is repeatedly shuffled.

Char.s

List Position.i()

Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()

CloseConsole()

Sample output:

<pre>abracadabra, daabarbraac, (0)

up, pu, (0)

a, a, (1)</pre>

=={{header|Python}}==

===Swap if it is locally better algorithm===

With added randomization of swaps!

 

def count(w1,wnew):

if i != j and wnew[j] != wnew[i] and w[i] != wnew[j] and w[j] != wnew[i]:

wnew[j], wnew[i] = wnew[i], wnew[j]

wnew = ''.join(wnew)

return wnew, count(w, wnew)

for w in test_words:

wnew, c = best_shuffle(w)

 

;Sample output

 

===Alternative algorithm #1===

 

 

def best_shuffle(s):

r.append(best)

count[best] -= 1

 

# If the final letter became stuck (as "ababcd" became "bacabd",

for s in "abracadabra", "seesaw", "elk", "grrrrrr", "up", "a":

shuffled, score = best_shuffle(s)

 

Output: <pre>abracadabra, raabarabacd, (0)

up, pu, (0)

a, a, (1)</pre>

 

 

 

 

 

 

 

 

 

 

<pre>

</pre>

 

{{works with|Ruby|1.9}}

 

# Fill _pos_ with positions in the order

# that we want to fill them.

pos = []

end

# Now fill in _new_ with _letters_ according to each position

# in _pos_, but skip ahead in _letters_ if we can avoid

new = "?" * s.length

until letters.empty?

end

score = new.chars.zip(s.chars).count { |c, d| c == d }

[new, score]

end

 

 

seesaw, essewa, (0)

elk, lke, (0)

grrrrrr, rgrrrrr, (5)

up, pu, (0)

 

=={{header|Scheme}}==

(define count

(lambda (str1 str2)

(number->string (count str shuffled)) ")\n"))))

'("abracadabra" "seesaw" "elk" "grrrrrr" "up" "a"))