Knuth shuffle

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.

BASIC

This method was specifically written to shuffle a standard poker deck, but can easily be changed to handle arrays of arbitrary size and/or type. <lang qbasic> RANDOMIZE TIMER

DIM unShuffled(51) AS STRING * 2 DIM Shuffled(51) AS STRING * 2 DIM L0 AS LONG, card AS LONG

DATA "AS","2S","3S","4S","5S","6S","7S","8S","9S","TS","JS","QS","KS" DATA "AH","2H","3H","4H","5H","6H","7H","8H","9H","TH","JH","QH","KH" DATA "AC","2C","3C","4C","5C","6C","7C","8C","9C","TC","JC","QC","KC" DATA "AD","2D","3D","4D","5D","6D","7D","8D","9D","TD","JD","QD","KD"

PRINT "before:" FOR L0 = 0 TO 51

   READ unShuffled(L0)
   PRINT unShuffled(L0); " ";

   card = INT(RND * (L0 + 1))
   Shuffled(L0) = unShuffled(card)
   IF card <> L0 THEN unShuffled(card) = unShuffled(L0)

   PRINT Shuffled(L0); " ";

NEXT </lang>

Output:

before:
AS 2S 3S 4S 5S 6S 7S 8S 9S TS JS QS KS AH 2H 3H 4H 5H 6H 7H 8H 9H TH JH QH KH AC
 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC AD 2D 3D 4D 5D 6D 7D 8D 9D TD JD QD KD

after:
KH TS 4D 5H 2D AC KS 5S 3H 5C 8D TC 8C AS 9D 7D QD AH KD 4C 2S 8H 7S AD JH 2H 6S
 QS 3S TH 3C 8S 4S QC QH 9H 6C 9C KC 9S TD 6H JD JC JS 7C 5D 4H 6D 7H 3D 2C

C

Works with: gcc

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>

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

Works with: Fortran version 90 and later

<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

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

Translation of: Tcl

<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'