Intro
The Fisher-Yates Shuffle algorithm is an algorithm for shuffling a finite sequence of elements in a linear data strucutre. For example, in a list of elements, it continuously determines the next element in the shuffled sequence randomly from the original list.
The resulting sequence is an unbiased permutation, where each is equally likely to happen.
The modern version’s time complexity is proportional to n which means it’s but happens in place.
Original Algorithm
The basic method given for generating a random permutation of the numbers 1 through N goes as follows:
- Write down the numbers from 1 through N.
- Pick a random number k between one and the number of unstruck numbers remaining (inclusive).
- Counting from the low end, strike out the _k_th number not yet struck out, and write it down at the end of a separate list.
- Repeat from step 2 until all the numbers have been struck out.
- The sequence of numbers written down in step 3 is now a random permutation of the original numbers.
Modern version
This version was designed to be used by computers and was introduced in the book The Art of Computer Programming. Avoids needlessly spending time counting the remaining numbers in step 3, by moving the “struck” to the end of the list and swapping them by the last unstruck number on each iteration. Reducing it from to .
-- To shuffle an array _a_ of _n_ elements (indices 0.._n_-1):
**for** _i_ **from** _n_−1 **down to** 1 **do**
_j_ ← random integer such that 0 ≤ _j_ ≤ _i_
exchange _a_[_j_] and _a_[_i_]
An equivalent version which shuffles the array in the opposite direction (from lowest index to highest) is:
-- To shuffle an array _a_ of _n_ elements (indices 0.._n_-1):
**for** _i_ **from** 0 **to** _n_−2 **do**
_j_ ← random integer such that _i_ ≤ _j_ ≤ _n-1_
exchange _a_[_i_] and _a_[_j_]