Mathwords logoMathwords

Fisher-Yates Shuffle — Definition, Formula & Example

The Fisher-Yates shuffle, also called the Knuth shuffle, is an algorithm that puts a list in a random order. It is fair: every possible arrangement is equally likely.

Given an array a1,a2,…,ana_1, a_2, \dots, a_n, for each i=n,n−1,…,2i = n, n-1, \dots, 2 choose an integer jj uniformly at random from {1,2,…,i}\{1, 2, \dots, i\}, independently of all earlier choices, and swap aia_i with aja_j. The resulting permutation is uniformly distributed over all n!n! permutations. The algorithm uses n−1n-1 random draws and runs in O(n)O(n) time.

Key Formula

P(a specific ordering)=1n⋅1n−1⋯12=1n!P(\text{a specific ordering}) = \frac{1}{n}\cdot\frac{1}{n-1}\cdots\frac{1}{2} = \frac{1}{n!}
Where:
  • nn = Number of items in the list
  • n!n! = Number of possible orderings of the n items

How It Works

Work from the last position to the front. At step ii, pick a random position jj from 11 to ii and swap that item into position ii. After this swap, position ii is never touched again, so the list splits into a shrinking unshuffled front and a growing finished back. Picking j=ij = i is allowed and leaves the item where it is. Proof of fairness: step ii has ii equally likely choices, so there are n(n−1)⋯2=n!n(n-1)\cdots 2 = n! equally likely choice sequences. You can recover each sequence from the final arrangement by reading positions n,n−1,…n, n-1, \dots in turn, so different sequences always give different permutations. That makes the map a bijection onto all n!n! permutations, and each permutation has probability 1/n!1/n!.

Worked Example

Problem: Shuffle the list A, B, C, D with Fisher-Yates. The random draws are j=2j = 2 (from 1–4), then j=3j = 3 (from 1–3), then j=1j = 1 (from 1–2). What is the final order, and how likely was it?
Step 1: For i=4i = 4, draw j=2j = 2. Swap positions 4 and 2. Position 4 now holds its final item.
A,B,C,D  →  A,D,C,BA,B,C,D \;\to\; A,D,C,B
Step 2: For i=3i = 3, draw j=3j = 3. Swapping a position with itself changes nothing. Then for i=2i = 2, draw j=1j = 1 and swap positions 2 and 1.
A,D,C,B  →  A,D,C,B  →  D,A,C,BA,D,C,B \;\to\; A,D,C,B \;\to\; D,A,C,B
Step 3: Each draw had a fixed number of equally likely options, and the draws are independent. Multiply their probabilities.
14⋅13⋅12=124=14!\frac{1}{4}\cdot\frac{1}{3}\cdot\frac{1}{2} = \frac{1}{24} = \frac{1}{4!}
Answer: The final order is D, A, C, B. Its probability is 124\frac{1}{24}, the same as each of the other 23 orderings of four items.

Why It Matters

Card-game software, playlist shuffles, and statistical permutation tests all need unbiased random orderings. Python's random.shuffle uses this method. Its correctness proof is a standard counting-bijection argument in discrete math and algorithms courses.

Common Mistakes

Mistake: Choosing jj from all nn positions at every step instead of from 11 to ii.
Correction: That version makes nn−1n^{n-1} equally likely choice sequences (nn choices at each of n−1n-1 steps). For n≥3n \ge 3, nn−1n^{n-1} is not divisible by n!n!, so the orderings cannot all be equally likely. For n=3n = 3, 9 sequences cannot split evenly among 6 orderings. Shrink the range to 11 through ii.

Related Terms