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

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

#### GET YOUR FREE ESTIMATE

Contact us today to discuss your goals and we will create a simple roadmap to get you there. We look forward to speaking with you!

### Main Office

Phone:   1 587-834-6567
Email:   support@ahtcloud.com
32 Westwinds Crescent NE #130
Calgary, AB T3J 5L3, CA

#### Products

TMS
Cloud Based Transportation Management System

https://www.ahttms.com
https://www.cloud.ahttms.com

#### Hours Of Operation

Monday 8:00 am - 5:00 pm 8:00 am - 5:00 pm 8:00 am - 5:00 pm 8:00 am - 5:00 pm 8:00 am - 5:00 pm Closed Closed