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>
BASIC
<lang qbasic> RANDOMIZE TIMER
DIM unShuffled(51) AS INTEGER DIM Shuffled(51) AS INTEGER DIM L0 AS LONG, card AS LONG
PRINT "before:" FOR L0 = 0 TO 51
unShuffled(L0) = L0 PRINT LTRIM$(STR$(unShuffled(L0))); " ";
NEXT
FOR L0 = 51 TO 0 STEP -1
card = INT(RND * (L0 + 1)) Shuffled(L0) = unShuffled(card) IF card <> L0 THEN unShuffled(card) = unShuffled(L0)
NEXT
PRINT : PRINT : PRINT "after:" FOR L0 = 0 TO 51
PRINT LTRIM$(STR$(Shuffled(L0))); " ";
NEXT </lang>
Sample output:
before: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 after: 37 5 4 12 29 25 34 20 40 23 31 1 14 6 18 15 50 38 45 0 30 28 24 26 21 11 16 41 2 42 48 35 36 49 7 22 32 44 33 43 9 13 8 51 17 39 27 47 3 10 46 19
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>
C++
Compiler: g++ (version 4.3.2 20081105 (Red Hat 4.3.2-7))
<lang cpp>#include <cstdlib>
- include <algorithm>
- include <iterator>
template<typename RandomAccessIterator> void knuthShuffle(RandomAccessIterator begin, RandomAccessIterator end) {
srand(time(0));
for(unsigned int n = end - begin - 1; n >= 1; --n) { unsigned int k = rand() % (n + 1); if(k != n) { std::iter_swap(begin + k, begin + n); } }
} </lang>
Common Lisp
<lang lisp>(defun nshuffle (sequence)
(loop for i from (length sequence) downto 2 do (rotatef (elt sequence (random i)) (elt sequence (1- i)))) sequence)</lang>
This operates on arbitrary sequences, but will be inefficient applied to a list as opposed to a vector. Dispatching on type, and using an intermediate vector to hold the contents of list can make both cases more efficient (since the array specific case can use aref
rather than elt
):
<lang lisp>(defun nshuffle (sequence)
(etypecase sequence (list (nshuffle-list sequence)) (array (nshuffle-array sequence))))
(defun nshuffle-list (list)
"Shuffle the list using an intermediate vector." (let ((array (nshuffle-array (coerce list 'vector)))) (declare (dynamic-extent array)) (map-into list 'identity array)))
(defun nshuffle-array (array)
(loop for i from (length array) downto 2 do (rotatef (aref array (random i)) (aref array (1- i))) finally (return array)))</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>
Forth
<lang forth> include random.fs
- shuffle ( deck size -- )
2 swap do dup i random cells + over @ over @ swap rot ! over ! cell+ -1 +loop drop ;
- .array 0 do dup @ . cell+ loop drop ;
create deck 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ,
deck 10 2dup shuffle .array </lang>
Fortran
<lang fortran>program Knuth_Shuffle
implicit none
integer, parameter :: reps = 1000000 integer :: i, n integer, dimension(10) :: a, bins = 0, initial = (/ (n, n=1,10) /)
do i = 1, reps a = initial call Shuffle(a) where (a == initial) bins = bins + 1 ! skew tester end do write(*, "(10(i8))") bins
! prints 100382 100007 99783 100231 100507 99921 99941 100270 100290 100442
contains
subroutine Shuffle(a)
integer, intent(inout) :: a(:) integer :: i, randpos, temp real :: r
do i = size(a), 2, -1 call random_number(r) randpos = int(r * i) + 1 temp = a(randpos) a(randpos) = a(i) a(i) = temp end do
end subroutine Shuffle
end program Knuth_Shuffle </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>
Logo
<lang logo> to swap :i :j :a
localmake "t item :i :a setitem :i :a item :j :a setitem :j :a :t
end to shuffle :a
for [i [count :a] 2] [swap 1 + random :i :i :a]
end
make "a {1 2 3 4 5 6 7 8 9 10} shuffle :a show :a </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
OCaml
<lang ocaml>let shuffle arr =
for n = Array.length arr - 1 downto 1 do let k = Random.int (n + 1) in let temp = arr.(n) in arr.(n) <- arr.(k); arr.(k) <- temp done</lang>
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'