Posted on by Martin Roberts

The Fisher-Yates Algorithm

Creating unbiased random permutations of lists is often crucial to sampling. The Fisher-Yates shuffle is the definitive method to shuffle a sequence of items. Popularised by Knuth, it is unbiased, has optimal linear time efficiency; uses constant space; and is incremental.

The modern Fisher-Yates algorithm is both elegant in its design and efficient at run-time.  Although it looks stunningly simple, this algorithm is unbiased, uses constant memory as it does in-place shuffling, and has optimal linear time efficiency

In pseudo-code, it is simply:

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

 

Discussion

Despite its simplicty, when developers attempt to code this from scratch it is extremely common that they make ‘off by one’ errors, which results in a notably biased permutation. Most notably, it is of critical importance to note that in the correct implementation, it is possible that an item is to be ‘swapped with itself.’ (that is, $j=i$).

Click here to see the definitive video explanation of the Fisher-Yates by Prof Sedgewick .

Note that Sedgewick is the author of one of the most readable and respected books on this topic! Over 900 pages of amazing content all for free!

Course:
PDF:
Code:
Solutions:

 

 

 

 

 

 

 

 

 

 

 

 

 

Code

Thanks to the Rosetta code, here is the modern Fisher-Yates algorithm in some of the common languages. (Note that if the language has an internal shuffle, this is typically mentioned first. Even though it is obviously preferable to use internal shuffling if its available, it is still very illuminating to see how the modern Fisher-Yates algorithm could be implemented in your language of choice.

 

C++

#include <algorithm>
#include <vector>
 
int main()
{
    int array[] = { 1,2,3,4,5,6,7,8,9 }; // C-style array of integers
    std::vector<int> vec(array, array + 9); // build STL container from int array
 
    std::random_shuffle(array, array + 9); // shuffle C-style array
    std::random_shuffle(vec.begin(), vec.end()); // shuffle STL container
}

#include <cstdlib>
#include <algorithm>
#include <iterator>
 
template<typename RandomAccessIterator>
void knuthShuffle(RandomAccessIterator begin, RandomAccessIterator end) {
  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);
    }
  }
}

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;
    }
}

JavaScript (ES5)

function knuthShuffle(arr) {
    var rand, temp, i;
 
    for (i = arr.length - 1; i > 0; i -= 1) {
        rand = Math.floor((i + 1) * Math.random());//get random between zero and i (inclusive)
        temp = arr[rand];//swap i and the zero-indexed number
        arr[rand] = arr[i];
        arr[i] = temp;
    }
    return arr;
}
 
var res = {
    '1,2,3': 0, '1,3,2': 0,
    '2,1,3': 0, '2,3,1': 0,
    '3,1,2': 0, '3,2,1': 0
};
 
for (var i = 0; i < 100000; i++) {
    res[knuthShuffle([1,2,3]).join(',')] += 1;
}
 
for (var key in res) {
    print(key + "\t" + res[key]);
}

Mathematica 

RandomSample[Range[n]]


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}
   ];
  input[[indices]]
  ]

 

MatLab

function list = knuthShuffle(list)
 
    for i = (numel(list):-1:2)  
 
        j = floor(i*rand(1) + 1); %Generate random int between 1 and i
 
        %Swap element i with element j.
        list([j i]) = list([i j]);    
    end
end

Python

from random import randrange
 
def knuth_shuffle(x):
    for i in range(len(x)-1, 0, -1):
        j = randrange(i + 1)
        x[i], x[j] = x[j], x[i]
 
x = list(range(10))
knuth_shuffle(x)

R

fisheryatesknuthshuffle <- function(n)
{
   a <- seq_len(n)
   while(n >=2)
   {     
      k <- sample.int(n, 1)
      if(k != n)
      {
         temp <- a[k]
         a[k] <- a[n]
         a[n] <- temp
      }
      n <- n - 1
   }
   a
}


***
My name is Martin Roberts. I have a PhD  in theoretical physics. I love maths and computing. I’m open to new opportunities – consulting, contract or full-time – so let’s have a chat on how we can work together!
Come follow me on Twitter: @Techsparx!
 My other contact details can be found here. [mc4wp_form id=”1021″]
Other Posts you may like