eduKate Sengkang

Small Group Tutorials

Here to help students catch up, keep up, and move ahead. Book a consultation here.

Chat on WhatsApp

How to Learn Fisher–Yates Shuffle: Uniform Permutations, Swap Invariants, Modulo Bias and Production-Grade Randomness

Wait, What?

A shuffle can look random and still be mathematically unfair.

The Fisher–Yates shuffle is one of the cleanest algorithms for teaching the difference between “seems random” and “is uniformly distributed.” Given an array of n items, it produces a random permutation in O(n) time using exactly n−1 swaps in its common in-place form. The code is tiny. The reasoning is not.

That makes Fisher–Yates an unusually strong Learning Hall article: a beginner can implement it in minutes, while a professional still has to reason about unbiased bounded-integer generation, PRNG state, reproducibility, cryptographic requirements, period limits, parallelism and statistical validation.

Quick Answer

Learn Fisher–Yates through permutation counting → bad shuffle examples → shrinking choice range → swap invariant → proof of uniformity → bounded random integers → modulo bias → reproducible PRNGs → security-grade randomness → testing and production contracts.

1. First define what “fair shuffle” means

For n distinct items, there are n! possible permutations. A uniform shuffle should produce each permutation with probability exactly:

1 / n!

If one ordering is more likely than another, the shuffle is biased even if nobody can spot the bias by looking at a few outputs.

2. A seductive wrong algorithm

A common mistake is:

for i from 0 to n-1:
    j = random integer from 0 to n-1
    swap(a[i], a[j])

It performs n random choices, each with n possibilities, so there are n^n possible sequences of choices. Those choice sequences cannot in general divide evenly among n! final permutations. Some permutations therefore receive more paths than others.

This is a valuable educational pattern: local randomness does not guarantee global uniformity.

3. The modern in-place Fisher–Yates loop

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

At step i, the algorithm chooses uniformly which of the remaining i+1 items will occupy position i. Once placed, that position is never touched again.

4. The invariant that makes the proof easy

After completing the iteration for index i, the suffix a[i..n−1] contains uniformly selected distinct items in their final positions, and the prefix a[0..i−1] contains exactly the unplaced items.

At the first step, each item has probability 1/n of landing in position n−1. At the next step, conditioned on not having been chosen already, each remaining item has probability 1/(n−1) of landing in position n−2. Continuing this way gives every complete ordering probability:

(1/n) * (1/(n-1)) * ... * (1/2) * 1 = 1/n!

That is the whole proof. The algorithm is short because the invariant carries the complexity.

5. Work n = 3 by hand

Start with [A,B,C]. At i=2, choose j from {0,1,2}. Each choice gives one of A, B or C a 1/3 chance of occupying the last slot. Then at i=1, choose between the two remaining items with probability 1/2. The final item is forced into position 0. Therefore each of the six permutations has probability 1/3 × 1/2 = 1/6.

Draw this as a small probability tree. Then draw the tree for the wrong “swap with any position every time” algorithm. The difference becomes visible rather than merely asserted.

6. Complexity is simple—but state the whole contract

The in-place shuffle performs O(n) work and O(1) auxiliary storage, excluding the random-number generator state. The standard form performs exactly n−1 swaps. But a production complexity statement should also acknowledge the cost of generating unbiased random integers. If bounded sampling uses rejection, a small variable amount of PRNG work may occur per iteration.

7. Modulo bias is where beginner code becomes professional code

Suppose a random generator outputs uniformly from 0 to 255, and you need an integer from 0 to 5. A tempting conversion is:

j = random_byte % 6

But 256 is not divisible by 6. Some remainders occur 43 times among the 256 inputs and others only 42 times. That creates systematic bias. The Fisher–Yates proof assumes each j is truly uniform over its required range; biased integer generation breaks the proof.

Common library implementations avoid this using rejection sampling or other unbiased range-reduction techniques. Do not reintroduce modulo bias around a high-quality PRNG.

8. Pseudorandom is not the same as cryptographically unpredictable

For games, simulations, randomized tests and reproducible experiments, a conventional pseudorandom generator may be appropriate. For card games involving money, lotteries, tokens, secret arrangements or security-sensitive protocols, unpredictability becomes part of the contract.

Python’s current random documentation describes a general-purpose pseudorandom module, while secrets exists for cryptographically strong randomness. NIST’s SP 800-90 family addresses construction and use of random-bit generators in security contexts. A fair combinatorial algorithm cannot compensate for a predictable source of random bits.

9. Reproducibility is often desirable

In scientific code, test harnesses and procedural generation, you may want exactly the opposite of secrecy: repeatability. Store the RNG algorithm, seed and sometimes full state. Merely storing “seed = 42” is not sufficient for long-term reproducibility if a library later changes its generator or bounded-integer mapping.

Professional systems distinguish deterministic reproducibility from unpredictability. Both are legitimate goals, but they require different random sources and operational policies.

10. The generator period creates another subtle limit

An RNG with finite internal state can generate only finitely many distinct output streams. Python documentation has long highlighted that for sufficiently long sequences, the number of possible permutations can exceed the period of a generator such as Mersenne Twister. Therefore a shuffle can be locally unbiased at each step while the generator’s global state space is still too small to reach every theoretical permutation of an enormous list.

This usually does not matter for ordinary lists, but it is a useful professional reminder: algorithmic uniformity is conditional on the random source model.

11. Inside-out Fisher–Yates

When building a shuffled array from an immutable input or generating a random permutation incrementally, an inside-out variant is useful. At step i, choose j uniformly from [0,i], copy the current value at j to the new slot i, and place the new input item at j. It preserves the same uniform-permutation reasoning while constructing the output rather than mutating the input.

12. Do not shuffle by sorting random keys

Another tempting pattern assigns every item a random key and sorts by that key. This has several problems: O(n log n) work, collisions when keys come from a finite range, ambiguity in tie handling, and dependence on sorting stability. It can be made correct with sufficiently rich unique random keys, but Fisher–Yates is simpler, faster and easier to prove.

13. Testing a shuffle is harder than testing a deterministic function

Every output can be a valid permutation, yet the distribution can still be wrong. Use layers of tests:

  • Structural tests: length unchanged, every input item appears exactly once.
  • Deterministic mock-RNG tests: feed known bounded choices and verify exact swap paths.
  • Small exhaustive distribution tests: for n = 3 or 4, run many trials and compare permutation frequencies.
  • Position tests: each item should appear in each position with approximately equal frequency.
  • Random-source tests: validate the bounded-integer generator separately.

Statistical tests cannot prove correctness on their own, but they are excellent at detecting gross implementation mistakes. The mathematical proof and the tests have different jobs.

14. Parallel Fisher–Yates is not just “split the array”

The classic in-place loop has sequential dependencies because later swap ranges shrink based on indices already finalized. Naïvely shuffling chunks independently does not produce a uniform permutation of the full array. Large-scale parallel random permutation needs a separate design: random-key methods with enough entropy, divide-and-conquer permutation algorithms, routing approaches, or carefully proven distributed schemes.

This is a useful boundary lesson: an O(n) sequential algorithm is not automatically the right algorithm at distributed scale.

15. How to learn it efficiently

Start with prediction. For a three-item list, give the learner a fixed stream of choices and ask for the final permutation. Then run the code. Investigate why the random range shrinks. Modify the loop into the wrong full-range swap version and compare empirical frequencies. Finally make an implementation that accepts an injected bounded-integer RNG.

This is consistent with PRIMM. Use subgoal labels such as Choose final position → Draw uniformly from unplaced prefix → Swap chosen item into final position → Shrink unresolved region. Subgoal-labelled worked examples have shown benefits in programming education, and faded worked examples can reduce support as learners become more independent.

Common failure states

  • Choosing j from the full array at every iteration.
  • Using an exclusive upper bound incorrectly and never allowing j = i.
  • Using random() * i with floating-point edge errors instead of a proper bounded-integer API.
  • Reducing raw random bits with modulo when the range does not divide evenly.
  • Using a predictable PRNG in a security-sensitive shuffle.
  • Reseeding inside the loop.
  • Assuming statistical-looking output proves uniformity.
  • Shuffling chunks independently and calling the result a global uniform permutation.
  • Failing to record RNG algorithm/state when reproducibility matters.

Practice ladder

  • Beginner: trace n = 3 by hand and prove all six outcomes have probability 1/6.
  • Foundation: implement in-place Fisher–Yates using a library bounded-integer generator.
  • Intermediate: write a deliberately biased shuffle and detect it empirically.
  • Advanced: implement unbiased range reduction from raw random words using rejection sampling and test it separately.
  • Professional: define separate reproducible and security-sensitive shuffle APIs, document RNG guarantees, run distribution tests, and evaluate very large or parallel permutation strategies.

Learning Hall boundary

This article owns uniform random permutation with Fisher–Yates and the randomness engineering needed to preserve its proof. It does not replace reservoir sampling, the Alias Method, Monte Carlo methods, cryptographic RNG design, random-number testing standards or distributed random-permutation research.

Evidence and further reading

Professional rule: you understand Fisher–Yates when you can prove the 1/n! distribution, identify the exact assumption that each bounded choice is uniform, and explain why a correct shuffle algorithm can still fail its real-world contract if the random source is biased, predictable or unreproducible.