Randomized & Probabilistic

Fisher–Yates Shuffle

Shuffle a deck so every ordering is equally likely — one pass, one swap per card, no bias.

First, one shuffle: orange is the position being fixed, blue the random partner, green the locked tail. Then a grid of how often each value lands in each position — it flattens to uniform.

What you're seeing

First the algorithm runs once: walking from the last card down, each position is filled by swapping in a uniformly-random card chosen from itself and everything before it — once a position is set (green), it's never touched again. Then we run thousands of shuffles and tally, for every position, how often each value lands there. If the shuffle is fair, that grid should be perfectly flat — every value equally likely in every slot — and you can watch it converge to that uniform 1/n.

The rule

shuffle(a):
    for i = n-1 down to 1:
        j = uniform random integer in [0, i]   # inclusive!
        swap(a[i], a[j])

The detail that matters: j ranges over [0, i] — including i itself. Drawing j from [0, n) every time instead (the "naive" shuffle) is subtly biased and does not produce a uniform permutation.

The invariant

The guarantee is that every one of the n! orderings comes out with exactly equal probability 1/n!. The clean way to see it: when we fix position i (working downward), we choose uniformly among the i+1 candidates still in play, so each is placed there with probability 1/(i+1); multiplying across all steps gives 1/n · 1/(n−1) · … · 1/2 · 1 = 1/n! for any particular final arrangement. Because every permutation has the same probability and there are exactly n! of them, the distribution is uniform. The naive variant breaks this by counting n^(n−1) equally-likely swap-sequences, which is not divisible by n! for n > 2 — so some permutations must be over- or under-represented. This entry's test checks uniformity directly with a chi-square over all n! permutations.

The cost

TimeSpaceRandom draws Fisher–YatesO(n)O(1)n−1

One pass, one swap and one random number per element, in place — optimal. (Compare sorting by random keys, which is O(n log n) and needs care to break ties unbiasedly.) The only real subtlety is the random-integer generation: using random() mod (i+1) introduces modulo bias unless handled, and a too-small PRNG state can't even reach all n! permutations for large decks — the reason card-shuffling code needs a well-seeded, wide generator.

In the wild

Fisher–Yates is the way to shuffle: it backs random.shuffle in Python, Collections.shuffle in Java, and shuffle utilities across languages; it deals cards and randomizes playlists, draws random samples and permutation test orderings in statistics, and randomizes treatment assignment in experiments. Its cautionary twin is famous — in 2008 a browser ballot was shuffled with a biased sort(() => Math.random() − 0.5) comparator, skewing the order — a reminder that "just randomize it" is exactly where this unbiased one-liner earns its keep.

Try this

Let the sample size climb and watch the frequency grid go from blotchy to a flat, even field — every cell converging on 1/n (the green borders mark the converged ones). Shrink the number of cards and it flattens faster; there are simply fewer permutations to spread the probability across.

References

  1. Fisher, R. A. & Yates, F. Statistical Tables for Biological, Agricultural and Medical Research, 1938 (the original shuffle).
  2. Durstenfeld, R. "Algorithm 235: Random permutation." Communications of the ACM 7(7):420, 1964 — the modern in-place O(n) form.
  3. Knuth, D. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, §3.4.2 (Algorithm P). Addison-Wesley.