# Knuth shuffle

Knuth shuffle
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

Works with: gcc

This shuffles any "object"; it imitates qsort in the syntax.

<lang c>#include <stdlib.h>

1. 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>

1. include <algorithm>
2. 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()

1. value: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].diverge()

? shuffle(arr, entropy) ? arr

1. 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>

## M4

<lang M4> divert(-1) define(`randSeed',141592653) define(`rand_t',`eval(randSeed^(randSeed>>13))') define(`random',

```  `define(`randSeed',eval((rand_t^(rand_t<<18))&0x7fffffff))randSeed')
```

define(`for',

```  `ifelse(\$#,0,``\$0,
`ifelse(eval(\$2<=\$3),1,
`pushdef(`\$1',\$2)\$4`'popdef(`\$1')\$0(`\$1',incr(\$2),\$3,`\$4')')')')
```

define(`set',`define(`\$1[\$2]',`\$3')') define(`get',`defn(\$1[\$2])') define(`new',`set(\$1,size,0)') define(`deck',

```  `new(\$1)for(`x',1,\$2,
`set(`\$1',x,x)')`'set(`\$1',size,\$2)')
```

define(`show',

```  `for(`x',1,get(\$1,size),`get(\$1,x)`'ifelse(x,get(\$1,size),`',`, ')')')
```

define(`swap',`set(\$1,\$2,get(\$1,\$4))`'set(\$1,\$4,\$3)') define(`shuffle',

```  `define(`s',get(\$1,size))`'for(`x',1,decr(s),
`swap(\$1,x,get(\$1,x),eval(x+random%(s-x+1)))')')
```

divert

deck(`b',52) show(`b') shuffle(`b') show(`b') </lang>

Output:

```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, 52

6, 22, 33, 51, 35, 45, 16, 32, 7, 34, 10, 44, 5, 38, 43, 25, 29, 9, 37, 20, 21,
48, 24, 46, 8, 26, 41, 47, 49, 36, 14, 31, 15, 39, 12, 17, 13, 1, 3, 4, 27, 11,
28, 2, 19, 30, 42, 50, 18, 52, 40, 23
```

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

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

## Vedit macro language

The shuffle routine in Playing Cards shuffles text lines in edit buffer. This example shuffles numeric registers #0 to #19.

The output will be inserted in current edit buffer.

<lang vedit> // Test main

1. 90 = Time_Tick // seed for random number generator
2. 99 = 20 // number of items in the array

IT("Before:") IN for (#100 = 0; #100 < #99; #100++) {

```   #@100 = #100
Num_Ins(#@100, LEFT+NOCR) IT(" ")
```

} IN

Call("SHUFFLE_NUMBERS")

IT("After:") IN for (#100 = 0; #100 < #99; #100++) {

```   Num_Ins(#@100, LEFT+NOCR) IT(" ")
```

} IN Return

//-------------------------------------------------------------- // Shuffle numeric registers #0 to #nn // #99 = number of registers to shuffle (nn-1) //

SHUFFLE_NUMBERS:

for (#91 = #99-1; #91 > 0; #91--) {

```   Call("RANDOM")
#101 = Return_Value
#102 = #@101; #@101 = #@91; #@91 = #102
```

} Return

//-------------------------------------------------------------- // Generate random numbers in range 0 <= Return_Value < #91 // #90 = Seed (0 to 0x7fffffff) // #91 = Scaling (0 to 0x10000) //

RANDOM:
1. 92 = 0x7fffffff / 48271
2. 93 = 0x7fffffff % 48271
3. 90 = (48271 * (#90 % #92) - #93 * (#90 / #92)) & 0x7fffffff

Return ((#90 & 0xffff) * #91 / 0x10000) </lang>

Output:

```Before:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
After:
9 13 8 18 10 1 17 15 0 16 14 19 3 2 7 11 6 4 5 12 ```