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 arrayaofnelements (indices 0..n-1):forifromn−1downto1doj← random integer such that 0 ≤j≤iexchangea[j] anda[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: http://ow.ly/nKvN50lWAvj

PDF: http://ow.ly/lTG650lWAvk

Code: http://ow.ly/oQvD50lWAvm

Solutions: http://ow.ly/OcOg50lWAvl

# 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 foundhere.[mc4wp_form id=”1021″]