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 , for each choose an integer uniformly at random from , independently of all earlier choices, and swap with . The resulting permutation is uniformly distributed over all permutations. The algorithm uses random draws and runs in time.
Key Formula
Where:
- = Number of items in the list
- = Number of possible orderings of the n items
How It Works
Work from the last position to the front. At step , pick a random position from to and swap that item into position . After this swap, position is never touched again, so the list splits into a shrinking unshuffled front and a growing finished back. Picking is allowed and leaves the item where it is. Proof of fairness: step has equally likely choices, so there are equally likely choice sequences. You can recover each sequence from the final arrangement by reading positions in turn, so different sequences always give different permutations. That makes the map a bijection onto all permutations, and each permutation has probability .
Worked Example
Problem: Shuffle the list A, B, C, D with Fisher-Yates. The random draws are (from 1–4), then (from 1–3), then (from 1–2). What is the final order, and how likely was it?
Step 1: For , draw . Swap positions 4 and 2. Position 4 now holds its final item.
Step 2: For , draw . Swapping a position with itself changes nothing. Then for , draw and swap positions 2 and 1.
Step 3: Each draw had a fixed number of equally likely options, and the draws are independent. Multiply their probabilities.
Answer: The final order is D, A, C, B. Its probability is , 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 from all positions at every step instead of from to .
Correction: That version makes equally likely choice sequences ( choices at each of steps). For , is not divisible by , so the orderings cannot all be equally likely. For , 9 sequences cannot split evenly among 6 orderings. Shrink the range to through .
