Fisher Yates Shuffle Algorithm
Friday, October 9, 2020 (MDT)Author: Emad Zaamout
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.
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
The Fisher – Yates shuffle algorithm, works as follows: starting from the last element of the array, swap it with a randomly selected element that is between the 0, and the element we started with. The process is repeated, for the second last element, third last and so forth until we have processed all the elements in the array.
Assume that finding the randomly selected element has a time complexity of O(1); then the Fisher – Yates shuffler algorithm works shuffles an array in O(n).
3. Fisher Yates Algorithm 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.