Fisher–Yates — shuffling entrants
Weighted drawA way to shuffle entrants "truly fairly" and set the order (their seats). Fair means every ordering comes up with equal probability.
Can't we just shuffle randomly?
Just "pick two entrants and swap seats" many times, right? But nobody knows how many times is enough, and some orderings come up more often, so it may not be fair. Fisher–Yates finishes perfectly fair in exactly one pass.
Core idea — "fill one seat at a time"
There are 5 seats (the order). Starting from the last seat, decide "who sits here?"
- Last (5th) seat → any 1 of 5 people (5 options)
- The next (4th) seat → 1 of the remaining 4 (4 options)
- 3rd seat → 1 of the remaining 3 … and so on down to the 1st
In the computer, the picked entrant just "swaps seats" with the one in that seat. Entrants shuffle by changing seats.
Follow it seat by seat
Count it yourself
There are 5×4×3×2×1 = 120 ways to line up 5 entrants. Fisher–Yates picks "anyone among the remaining" at each seat, creating 120 paths, and each path makes a different ordering exactly once → every ordering is exactly 1/120.
With a small case of 3 (A·B·C), it is 3×2×1 = 6 ways.
| Case | 1st seat | 2nd seat | 3rd seat |
|---|---|---|---|
| 1 | A | B | C |
| 2 | A | C | B |
| 3 | B | A | C |
| 4 | B | C | A |
| 5 | C | A | B |
| 6 | C | B | A |
Is it really fair? — check over many shuffles
How many times "entrant No. 1" sat in each seat. If the bars are even, it is fair.
Total shuffles 0
- Durstenfeld, R. (1964). Algorithm 235: Random Permutation. Communications of the ACM, 7(7), 420.
- Fisher–Yates Shuffle. Wikipedia. en.wikipedia.org/wiki/Fisher-Yates_shuffle