Knuth shuffle
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
Implement the Knuth shuffle (aka the Fisher-Yates shuffle) for an integer array (or, if possible, an array of any type). The Knuth shuffle is used to create a random permutation of an array.
AutoHotkey
ahk forum: discussion <lang AutoHotkey>MsgBox % shuffle("1,2,3,4,5,6,7,8,9") MsgBox % shuffle("1,2,3,4,5,6,7,8,9")
shuffle(list) { ; shuffle comma separated list, converted to array
StringSplit a, list, `, ; make array (length = a0) Loop % a0-1 { Random i, A_Index, a0 ; swap item 1,2... with a random item to the right of it t := a%i%, a%i% := a%A_Index%, a%A_Index% := t } Loop % a0 ; construct string from sorted array s .= "," . a%A_Index% Return SubStr(s,2) ; drop leading comma
}</lang>
C
This shuffles any "object"; it imitates qsort in the syntax.
<lang c>#include <stdlib.h>
- include <string.h>
inline int rrand(int m) {
return (int)((double)m * ( rand() / (RAND_MAX+1.0) ));
}
void shuffle(void *obj, size_t nmemb, size_t size) {
void *temp = malloc(size); size_t n = nmemb; while ( n > 1 ) { size_t k = rrand(n--); memcpy(temp, obj + n*size, size); memcpy(obj + n*size, obj + k*size, size); memcpy(obj + k*size, temp, size); } free(temp);
}</lang>
E
<lang e>def shuffle(array, random) {
for bound in (2..(array.size())).descending() { def i := random.nextInt(bound) def swapTo := bound - 1 def t := array[swapTo] array[swapTo] := array[i] array[i] := t }
}</lang>
<lang e>? def arr := [1,2,3,4,5,6,7,8,9,10].diverge()
- value: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].diverge()
? shuffle(arr, entropy) ? arr
- value: [4, 5, 2, 9, 7, 8, 1, 3, 6, 10].diverge()</lang>
Java
<lang java>import java.util.Random;
public static final Random gen = new Random();
// version for array of ints public static void shuffle (int[] array) {
int n = array.length; while (n > 1) { int k = gen.nextInt(n--); //decrements after using the value int temp = array[n]; array[n] = array[k]; array[k] = temp; }
} // version for array of references public static void shuffle (Object[] array) {
int n = array.length; while (n > 1) { int k = gen.nextInt(n--); //decrements after using the value Object temp = array[n]; array[n] = array[k]; array[k] = temp; }
}</lang>
Mathematica
Usage of built-in function: <lang Mathematica>RandomSample[{1, 2, 3, 4, 5, 6}]</lang> Custom function: <lang Mathematica> Shuffle[input_List /; Length[input] >= 1] :=
Module[{indices = {}, allindices = Range[Length[input]]}, Do[ AppendTo[indices, Complement[allindices, indices][[RandomInteger[{1, i}]]]]; , {i, Length[input], 1, -1} ]; inputindices ]
</lang> Example: <lang Mathematica>Shuffle[{1, 2, 3, 4, 5, 6}]</lang>
Modula-3
<lang modula3>MODULE Shuffle EXPORTS Main;
IMPORT IO, Fmt, Random;
VAR a := ARRAY [0..9] OF INTEGER {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
PROCEDURE Shuffle(VAR a: ARRAY OF INTEGER) =
VAR temp: INTEGER; n: INTEGER := NUMBER(a);
BEGIN
WITH rand = NEW(Random.Default).init() DO WHILE n > 1 DO WITH k = rand.integer(0, n - 1) DO DEC(n); temp := a[n]; a[n] := a[k]; a[k] := temp; END; END; END;
END Shuffle;
BEGIN
Shuffle(a); FOR i := FIRST(a) TO LAST(a) DO IO.Put(Fmt.Int(a[i]) & " "); END; IO.Put("\n");
END Shuffle.</lang> Output:
martin@thinkpad:~$ ./shuffle 9 2 7 3 6 8 4 5 1 10 martin@thinkpad:~$ ./shuffle 1 7 8 10 5 4 6 3 9 2
Perl
<lang perl>sub shuffle
{my @a = @_; foreach my $n (1 .. $#a) {my $k = int rand $n + 1; $k == $n or @a[$k, $n] = @a[$n, $k];} return @a;}</lang>
Python
<lang python>
Fisher Yates(Knuth) Random shuffle.
Closely follows: http://en.wikipedia.org/wiki/Knuth_shuffle#Examples
from random import randint
MIN,MAX = 0,1
def fisheryates_shuffle(Scratch):
Range = [1, len(Scratch)] Result = [] while Range > [1,0]: Roll = randint(*Range) Result.append( Scratch.pop(Roll-1) ) Range[MAX] -= 1 # inplace result Scratch[:] = Result
def fisheryatesknuth_shuffle(ScratchResult):
Range = [1, len(ScratchResult)] while Range > [1,0]: Roll = randint(*Range) # result computed inplace ScratchResult[Roll-1], ScratchResult[Range[MAX]-1] = ( ScratchResult[Range[MAX]-1], ScratchResult[Roll-1] ) Range[MAX] -= 1
x=[1,2,3,4,5,6,7,8] copyofx = x[:] id_pre = id(x) fisheryates_shuffle(x) id_post = id(x) assert id_pre == id_post, "Should be an in-place shuffle" print ("Fisher-Yates:", x)
x = copyofx id_pre = id(x) fisheryatesknuth_shuffle(x) id_post = id(x) assert id_pre == id_post, "Should be an in-place shuffle" print ("Fisher-Yates-Knuth:", x)</lang> Sample output
Fisher-Yates: [1, 5, 7, 8, 6, 2, 4, 3] Fisher-Yates-Knuth: [8, 7, 2, 5, 4, 3, 1, 6]
The above functions work on lists of anything such as this list of mixed integers and strings:
>>> x = ['do', 're', 'mi', 'fa', 'so', 3, 2, 1, 0] >>> fisheryates_shuffle(x) >>> x ['so', 'fa', 3, 're', 2, 1, 0, 'do', 'mi'] >>> x = ['do', 're', 'mi', 'fa', 'so', 3, 2, 1, 0] >>> fisheryatesknuth_shuffle(x) >>> x [3, 're', 0, 'so', 'fa', 'mi', 2, 1, 'do'] >>>
And works with nothing
>>> x=[] >>> fisheryatesknuth_shuffle(x) >>> x [] >>> fisheryates_shuffle(x) >>> x [] >>>
To get some idea of how 'good' the shuffle is this checks how many times each digit of a 10 digit range is shuffled back to its original position (should approximate reps/10): <lang python>>>> def shuffle_skew_tester(f, n=10, reps=100000): bins = [0]*n toshuffle = list(range(n)) for i in range(reps): shuffled = toshuffle[:] # copy f(shuffled) # count how many times shuffle leaves something in same place for j,k in enumerate(shuffled): if j == k: bins[j] += 1 return bins
>>> shuffle_skew_tester(fisheryates_shuffle, reps=1000000) [99975, 100002, 99679, 99895, 99927, 100165, 100638, 99892, 100218, 99672] >>> shuffle_skew_tester(fisheryatesknuth_shuffle, reps=1000000) [99967, 99527, 99889, 99915, 100591, 100051, 99375, 100157, 100106, 99548] >>> >>> from random import shuffle # in-built routine >>> shuffle_skew_tester(shuffle, reps=1000000) [99998, 99496, 99886, 99923, 99946, 99937, 99721, 99982, 99904, 99958] >>> </lang>
Ruby
<lang ruby>class Array
def knuth_shuffle! j = length i = 0 while j > 1 r = i + rand(j) self[i], self[r] = self[r], self[i] i += 1 j -= 1 end self end
end
r = {} 100_000.times do |i|
a = [1,2,3].knuth_shuffle! if r[a] r[a] += 1 else r[a] = 1 end
end
r.keys.sort.each {|a| puts "#{a.inspect} => #{r[a]}"}</lang>results in
[1, 2, 3] => 16572 [1, 3, 2] => 16610 [2, 1, 3] => 16633 [2, 3, 1] => 16714 [3, 1, 2] => 16838 [3, 2, 1] => 16633
Tcl
<lang tcl>proc knuth_shuffle lst {
set j [llength $lst] for {set i 0} {$j > 1} {incr i;incr j -1} { set r [expr {$i+int(rand()*$j)}] set t [lindex $lst $i] lset lst $i [lindex $lst $r] lset lst $r $t } return $lst
}
% knuth_shuffle {1 2 3 4 5} 2 1 3 5 4 % knuth_shuffle {1 2 3 4 5} 5 2 1 4 3 % knuth_shuffle {tom dick harry peter paul mary} tom paul mary harry peter dick</lang> As a test of skewing (an indicator of a poor implementation) this code was used: <lang tcl>% for {set i 0} {$i<100000} {incr i} {
foreach val [knuth_shuffle {1 2 3 4 5}] pos {pos0 pos1 pos2 pos3 pos4} { incr tots($pos) $val }
} % parray tots tots(pos0) = 300006 tots(pos1) = 300223 tots(pos2) = 299701 tots(pos3) = 299830 tots(pos4) = 300240</lang>
Ursala
This function works on lists of any type and length, including character strings.
<lang Ursala> shuffle = @iNX ~&l->r ^jrX/~&l ~&lK8PrC</lang>
test program: <lang Ursala>#cast %s
example = shuffle 'abcdefghijkl'</lang> output:
'keacfjlbdigh'