# Fisher - Yates Shuffle Algorithm

Friday, October 9, 2020 (MDT)

### 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 AlgorithmHighest to Lowest Index Versionoutcome: Unbiased Random Shuffle forAcomplexity:O(n)input:A← array/list withnelementsi←0n← length ofAforifromn - 1to1doj← random integer between0andiswap(A[i],A[j])end

Fisher and Yates Array Shuffle AlgorithmLowest to Highest Index Versionoutcome: Unbiased Random Shuffle forAcomplexity:O(n)input:A← array/list withnelementsi←0n← length ofAforifrom0ton - 2doj← random integer betweeniandnswap(A[i],A[j])end

**How does the Fisher and Yates Shuffle Algorithm Work?**

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

#### TypeScript - Javascript ES6 Implementation

**fisher-yates-shuffle-algorithm.ts**

**driver.ts**

#### Implementation Testing - JIST

**fisher-yates-algorithm.spec.ts**

#### Javascript ES5 Implementation

**fisher-yates-algorithm-es5.js**

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