Fisher Yates Shuffle Algorithm

1. Introduction

Fisher and Yates (also known as the Knuth shuffle) is an algorithm used for creating an unbiased random permutation of arrays or lists, where unbiased randomness is crucial to the sampling. The Fisher and Yates algorithm has a linear complexity; uses a variable (constant) number of memory blocks; and can be used for generating the permutation incrementally as needed.

Sample Problem

Consider the following: Write a program to generate X unique random numbers where each number, is between 1 and X (inclusive).

By using the Fisher – Yates algorithm, we can accomplish this by creating a list that contains X elements (i.e. A = [1, 2, 3, ..., X]). We start from the last element of the array and keep iterating backwards until we reach the first element in our list; For each iteration, we swap the current element in our list, with a random element, whose index is between the 0, and the index, of the element at the given iteration. The end result will be a shuffled array whose elements, are unique random numbers between 1 to X inclusive.

2. Fisher Yates Algorithm Pseudocode

The Fisher and Yates algorithm has many usages such as shuffling decks of cards, generating random numbers, and much more. Below, we give 2 variations of the Fisher and Yates algorithm, written in Pseudocode. The first variation iterates through all the elements of the given array, starting from the last element, until we reach the first, while the second variation starts from the first elements, until we reach the last element in the array. Note that both variations achieve the same result, and complexity.

Fisher and Yates Array Shuffle Algorithm
Highest to Lowest Index Version 
outcome: Unbiased Random Shuffle for A
complexity: O(n)

input: A ← array/list with n elements

i ← 0
n ← length of A
for i from n - 1 to 1 do
    j ← random integer between 0 and i
    swap(A[i],A[j])
end

Fisher and Yates Array Shuffle Algorithm
Lowest to Highest Index Version 
outcome: Unbiased Random Shuffle for A
complexity: O(n)

input: A ← array/list with n elements

i ← 0
n ← length of A
for i from 0 to n - 2 do
    j ← random integer between i and n
    swap(A[i],A[j])
end

3. Fisher Yates Algorithm Implementation

Testing Fisher Yates in Javascript ES6 [JIST]

Testing Fisher Yates in Javascript ES6 [JIST]

Javascript ES5 Implementation

4. Testing Bias

For simplicity, assume we want to generate 3 random unique numbers between 1 and 3 inclusive. Notice that we have 6 possible outcomes: 123, 132, 213, 231, 321, 312.

To verify that Fisher – Yates algorithm produces unbiased results, we will generate 3, random unique numbers as described above, and we will repeat the process 10,000 times. By definition, a bias outcome is an outcome that is more likely to happen. Since we want unbiased results, we expect that after repeating the process 10,000 times, all possible outcomes would have the same number of occurrence or relatively close.