Fisher-Yates Shuffle: One Pass, 1/n! Guarantee, No Exceptions

Some developer is shuffling an array right now by picking a random index from the entire range at every step. It compiles. The tests pass. Their card game has been subtly cheating players for two years. Fisher-Yates solves this in one pass and comes with a proof.

The Mental Model: Two Zones and a Shrinking Live Pool

The Fisher-Yates shuffle algorithm is an in-place algorithm that produces a uniformly random permutation of an array in O(n) time and O(1) space. The mental model: divide the array into a live zone (elements not yet placed) and a fixed zone (elements already placed). At each step, pick a uniformly random element from the live zone and move it to the boundary between the two zones. Repeat until the live zone is empty.

You reach for it any time you need a fair shuffle, a random sample without replacement, or a random ordering that is proved correct rather than merely plausible. Python's random.shuffle, Java's Collections.shuffle, Ruby's Array#shuffle, and Go's rand.Shuffle all use this algorithm internally.

The live zone shrinks by one element per step. The fixed zone grows. Each placed element never moves again.

Three People Got Credit for One Algorithm

Ronald Fisher and Frank Yates described the original shuffle in their 1938 book "Statistical Tables for Biological, Agricultural and Medical Research." Their version required a paper table and O(n²) work. Richard Durstenfeld published the O(n) in-place variant in 1964 as "Algorithm 235: Random permutation" in Communications of the ACM. Donald Knuth included it in The Art of Computer Programming (Volume 2) as "Algorithm P," which is how most engineers encountered it. The algorithm now carrying Fisher and Yates's names is really Durstenfeld's improvement, but the attribution stuck.

Credit in computer science: distributed like a bad shuffle.

The Meme That Started as a Bug Report

Before the proof, a real Reddit post from r/ProgrammerHumor titled "theBugInFisherYates":

Someone simulated a million card shuffles to report a bug in Fisher-Yates. The code was correct. Python's random.randint(a, b) is inclusive on both ends. The bug was in the mental model, not the algorithm. This is a great argument for reading the proof.

How the Two Zones Work

The invariant at every step:

Live zone: arr[0..i]   Fixed zone: arr[i+1..n-1]

At step i, pick a uniformly random index j from [0, i] and swap arr[i] with arr[j]. After the swap, arr[i] is in its final position and joins the fixed zone. Decrement i. Repeat.

Here is a trace for [A, B, C, D, E]:

Start:   [ A  B  C  D  E ]   live=[0..4]  fixed=[]

i=4, j=1 chosen (B):
         [ A  E  C  D  B ]   live=[0..3]  fixed=[B]
                        ^^^

i=3, j=0 chosen (A):
         [ D  E  C  A  B ]   live=[0..2]  fixed=[A,B]
                   ^^^

i=2, j=2 chosen (C, no-op swap):
         [ D  E  C  A  B ]   live=[0..1]  fixed=[C,A,B]
                ^^^

i=1, j=0 chosen (D):
         [ E  D  C  A  B ]   live=[0..0]  fixed=[D,C,A,B]
            ^^^

Done: [ E  D  C  A  B ]

The loop runs from i = n-1 down to i = 1. The last element (i=0) is already in its position because it is the only element left in the live zone.

Yellow arcs are swaps. Green cells are permanently placed. Note step i=2, j=2: the element swaps with itself. That is not a bug. That is the algorithm allowing an element to stay put.

Why Every Permutation Has Probability Exactly 1/n!

The probability of any specific output permutation is 1/n!, the same as drawing elements blindly from a hat one at a time.

The argument is a telescoping product. At step i=n-1 you pick uniformly from n elements, so the probability of any specific choice is 1/n. At step i=n-2 you pick uniformly from n-1 remaining elements, giving 1/(n-1). Continue until i=1, where you pick from 2 elements with probability 1/2.

For a specific permutation to occur, each of these n-1 choices must land exactly right. Since the choices are independent:

P(specific permutation) = 1/n × 1/(n-1) × ... × 1/2 × 1/1 = 1/n!

For n=3, that is 1/6. There are exactly 6 permutations of three elements. The distribution is uniform by construction, not by approximation.

The algorithm has exactly n! equally likely execution paths, one per permutation. This is the key. The naive shuffle breaks this property.

Why the Naive Shuffle Is Wrong

The intuitive approach is to pick j from the entire range [0, n-1] at every step, not just [0, i]. This looks similar. It is wrong.

For [A, B, C] with n=3, the naive approach (pick from 0 to 2 at each of 3 steps) has 3^3 = 27 equally likely execution paths. There are 3! = 6 permutations. 27 is not divisible by 6, so no assignment of paths to permutations can be uniform. At least some permutations must appear more often than others. This is pigeonhole, not bad luck.

Here is the exact distribution the naive shuffle produces for [A, B, C], derived by tracing all 27 paths:

Permutation   Paths   Probability
[A, B, C]       4      4/27 ≈ 14.8%
[A, C, B]       5      5/27 ≈ 18.5%
[B, A, C]       5      5/27 ≈ 18.5%
[B, C, A]       4      4/27 ≈ 14.8%
[C, A, B]       5      5/27 ≈ 18.5%
[C, B, A]       4      4/27 ≈ 14.8%

Fisher-Yates: all six permutations at exactly 1/6 ≈ 16.7%

The bias grows with n. For n=10, 10^10 naive paths must distribute across 10! = 3,628,800 permutations, and the imbalance becomes systematic.

Three of the six permutations are 25% more likely than the others under the naive shuffle. No unit test will tell you this. It just quietly cheats.

The JavaScript Sort Hack Is Broken by Design

The common JavaScript shuffle uses arr.sort(() => Math.random() - 0.5). This ships in production codebases. It has two separate ways to be wrong, which is impressive.

First, it is the naive shuffle in disguise. The comparator is called O(n log n) times and each call produces an independent random number, producing far more than n! equally likely outcomes. Second, Array.sort requires a consistent, transitive comparator. Math.random() - 0.5 violates transitivity: the same pair of elements can compare differently on different calls. V8's sort algorithm uses the comparison results to make structural assumptions that break when those results are inconsistent. The resulting distribution depends on the engine and on array length, and it cannot be fixed by adjusting the comparator.

// Wrong. Biased, engine-dependent, and also sort of philosophically broken.
arr.sort(() => Math.random() - 0.5);

// Correct. Exactly n-1 swaps, proved uniform.
function shuffle(arr) {
    for (let i = arr.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}

The correct version picks j from [0, i] using Math.floor(Math.random() * (i + 1)). Note the i + 1: Math.random() returns [0, 1), so multiplying by i + 1 and flooring gives a uniform integer in [0, i] inclusive.

Why rand() % n Is Subtly Wrong

In C, rand() % (i + 1) has modulo bias when RAND_MAX + 1 is not divisible by i + 1. With RAND_MAX = 32767 and i + 1 = 3, the values 0, 1, 2 appear with frequencies 10923, 10922, 10922 out of 32768. Small, but mathematically guaranteed bias. The kind of bug that hides for years and only surfaces when someone runs a million shuffles.

On BSD and macOS, arc4random_uniform(i + 1) is cryptographically secure and unbiased. PHP's random_int(0, i) is also cryptographically secure and unbiased. Java's rng.nextInt(n) uses rejection sampling internally to eliminate bias. Python's random.randint(0, i) does the same.

In any language where you control the RNG call, prefer a function that takes a range and handles the bias elimination internally.

Sattolo's Algorithm: One Character Off, Completely Different

Change the upper bound from [0, i] to [0, i-1] (exclude i itself) and you get Sattolo's algorithm (1986). The resulting permutation is guaranteed to have no fixed points (no element in its original position) and to form a single cycle of length n.

# Fisher-Yates: any uniform permutation
j = random.randint(0, i)

# Sattolo's algorithm: single-cycle derangement
j = random.randint(0, i - 1)

These two algorithms differ by one character and produce fundamentally different distributions. Sattolo's output is not a uniform permutation. It is a uniform distribution over the subset of permutations that are single cycles. If you need a derangement with arbitrary cycle structure, neither algorithm gives that directly. Use a rejection approach on top of Fisher-Yates.

One character. Completely different mathematical object. Code review accordingly.

Stop After k Steps: Random Sampling Without Replacement

Fisher-Yates generalizes to random sampling: if you want k items from n with no repeats, run the algorithm for only k steps. The first k positions of the result form a uniform random k-subset of the original array.

import random

def random_sample(arr: list, k: int) -> list:
    arr = arr[:]
    n = len(arr)
    for i in range(k):
        j = random.randint(i, n - 1)   # forward variant: pick from [i, n-1]
        arr[i], arr[j] = arr[j], arr[i]
    return arr[:k]

No set of "already picked" elements, no retry loop, no hash table. This runs in O(k) time and O(k) space (copying the input to avoid mutation). For k close to n, just run the full shuffle and return the whole array.

Time and Space: Both Exact, Not Amortized

O(n) time is exact, not amortized. Every iteration does one RNG call and one swap, both O(1), with no rehashing, no resizing, and no retry paths. The algorithm does exactly n-1 swaps and terminates.

O(1) space is exact. The shuffle is in-place. No auxiliary array, no recursion, no stack. The only overhead is a loop variable and the temporary in the swap, which modern compilers handle via register allocation.

The only source of hidden cost is the RNG itself. A cryptographically secure RNG (arc4random, Java's SecureRandom) adds constant overhead per call but does not change the asymptotic bounds.

One Structure, Every Language

import random

def fisher_yates_shuffle(arr: list) -> None:
    n = len(arr)
    for i in range(n - 1, 0, -1):
        j = random.randint(0, i)  # randint is inclusive on both ends
        arr[i], arr[j] = arr[j], arr[i]

# random.shuffle(arr) uses this algorithm internally.

Where This Shows Up in the Real World

Card games and board games. Any game with a deck needs an unbiased shuffle. The two-zone mechanics map directly onto "deal from a shuffled deck": the fixed zone is the hand already dealt, the live zone is the remaining deck. Blackjack simulators, poker Monte Carlo evaluators, and board game engines all use this.

Random sampling without replacement. If you want k items from n with no repeats, the naive approach (pick, check a set, retry if already seen) is O(k) expected but degrades to O(n) per pick near k=n. The k-subset shortcut is O(k) worst case with no retries.

Monte Carlo simulations. Many simulations require random orderings of agents or events. A biased shuffle introduces systematic error that compounds across millions of simulation runs. Nobody finds this until someone runs a proper chi-squared test on the output distribution.

Test data generation. Randomizing test case order without bias ensures tests do not accidentally depend on insertion order.

Online selection. When you do not know the array length in advance, reservoir sampling generalizes Fisher-Yates to streams. The k-subset shortcut is the bridge between the two.

Load balancing. Shuffling a server list before round-robin assignment ensures no server is systematically favored for the first request in each cycle.

When the Fisher-Yates Shuffle Algorithm Is the Right Tool

The direct signals: the problem says "shuffle," "randomize the order," or "random permutation." A few subtler forms follow.

You need k items from n with no repeats and order matters. If the naive set approach feels awkward, it is. The k-subset shortcut handles this cleanly.

Your algorithm needs to survive adversarial inputs via randomization. Shuffling input before processing prevents worst-case inputs from being constructed by an adversary. Quicksort on sorted input is the canonical example. Shuffling the array first reduces this to expected O(n log n) with no worst-case trigger.

You see n! anywhere in a complexity argument. The number of permutations of n elements is n!, and Fisher-Yates generates one uniformly in O(n). When a brute-force over permutations would be O(n! × f(n)), ask whether you need all permutations or just a random one. The backtracking time complexity breakdown covers when you genuinely need all of them.

Worked Example 1: LeetCode 384, Shuffle an Array

Problem: implement shuffle() and reset() for an array. shuffle() must return a uniformly random permutation each time.

Why Fisher-Yates fits: direct application. Store the original array for reset(). For each shuffle() call, copy the original and run the algorithm in place.

import random

class Solution:
    def __init__(self, nums: list[int]):
        self.original = nums[:]
        self.arr = nums

    def reset(self) -> list[int]:
        self.arr = self.original[:]
        return self.arr

    def shuffle(self) -> list[int]:
        for i in range(len(self.arr) - 1, 0, -1):
            j = random.randint(0, i)
            self.arr[i], self.arr[j] = self.arr[j], self.arr[i]
        return self.arr

Time: O(n) per shuffle, O(n) per reset. Space: O(n) total for the stored original.

Worked Example 2: LeetCode 710, Random Pick with Blacklist

Problem: given N and a blacklist B, implement pick() to return a uniform random integer from [0, N) that is not in the blacklist.

Naive: build a list of all valid integers and pick uniformly. O(N) space, which fails when N is large.

The Fisher-Yates mental model gives an O(|B|) space solution. Divide [0, N) into two zones: the "lower zone" [0, N-|B|) and the "upper zone" [N-|B|, N). Some indices in the lower zone are blacklisted. Some indices in the upper zone are not blacklisted. Map each blacklisted lower-zone index to a non-blacklisted upper-zone index. This is exactly the lazy form of one Fisher-Yates swap per blacklisted index.

import random

class Solution:
    def __init__(self, n: int, blacklist: list[int]):
        self.bound = n - len(blacklist)
        blackset = set(blacklist)
        upper_white = [i for i in range(self.bound, n) if i not in blackset]
        self.remap: dict[int, int] = {}
        upper_idx = 0
        for b in blacklist:
            if b < self.bound:
                self.remap[b] = upper_white[upper_idx]
                upper_idx += 1

    def pick(self) -> int:
        idx = random.randint(0, self.bound - 1)
        return self.remap.get(idx, idx)

Each call to pick() runs in O(1). The remapping dictionary has at most |B| entries. The construction step is O(N) in the worst case (building upper_white scans the upper zone), but this can be reduced to O(|B| log |B|) with a smarter construction. The key insight is that the remap dictionary encodes the lazy Fisher-Yates swaps that a full shuffle would have applied.

The Short Version

• Fisher-Yates shuffles in place in O(n) exact time and O(1) exact space. No amortization, no hidden resizes.
• The two-zone invariant (live pool shrinks, fixed zone grows) is the mechanic. Each step moves one random element from live to fixed.
• Correctness proof: the probability of any specific permutation is 1/n × 1/(n-1) × ... × 1/1 = 1/n!. The algorithm has exactly n! equally likely execution paths.
• The naive shuffle (pick from [0, n-1] every step) has n^n paths for n elements. Since n^n is not divisible by n! for n >= 3, bias is guaranteed. There is no test that will catch this in a real codebase.
• arr.sort(() => Math.random() - 0.5) in JavaScript is wrong. It violates sort's transitivity requirement and produces engine-dependent bias.
• Sattolo's algorithm differs by one character (pick from [0, i-1] not [0, i]) and produces single-cycle derangements, not uniform permutations.
• rand() % n in C has modulo bias. Use arc4random_uniform on BSD/macOS or a rejection-sampling wrapper.
• The k-subset shortcut: stop after k steps for O(k) random sampling without replacement.

If you want to practice explaining the correctness proof out loud under time pressure, SpaceComplexity runs voice-based DSA mock interviews with rubric feedback. The proof has exactly the structure that distinguishes a strong hire from a correct answer.

For the streaming generalization of the k-subset shortcut, the reservoir sampling deep dive covers Algorithm R and Algorithm L in full. For the context of why n! makes brute-force over permutations expensive, the backtracking time complexity breakdown has the derivation. And for how comparison-based sorting's Ω(n log n) lower bound makes Fisher-Yates's O(n) feel surprising, the merge sort vs quicksort analysis is the right companion.

Further Reading

• Fisher-Yates shuffle, Wikipedia
• Fisher-Yates Algorithm, GeeksforGeeks
• std::shuffle, cppreference
• random.shuffle, Python 3 docs
• Durstenfeld, R. (1964). Algorithm 235: Random permutation. Communications of the ACM, 7(7), 420.