Shuffling done right
To shuffle an array so every ordering is equally likely, the Fisher Yates method walks from the last index toward the first. At each position it swaps the current element with one chosen uniformly from the positions at or before it.
- Each step fixes one final slot.
- The chosen range shrinks by one each time.
Why it is uniform
There are a fixed number of permutations, and the algorithm makes one independent uniform choice per step. Multiplying these choices gives exactly one over the number of permutations for every ordering, so no arrangement is favored.
The common bug
A tempting but wrong variant picks the swap partner from the whole array every time instead of the shrinking prefix. That produces a biased distribution where some permutations appear more often than others, a classic interview trap.
- Always draw from the valid shrinking range.
- Use an unbiased random integer for that range.
Key idea
Fisher Yates swaps each position with a uniformly chosen earlier or equal position, making one independent choice per slot so every permutation is equally likely, provided the partner is drawn only from the shrinking valid range.