Fisher-Yates Shuffle

Why Fisher-Yates Shuffle Matters

A quiz application needs to show the same six questions in a random order. A simulation needs a random ordering of participants. A card game needs a shuffled deck. All three require a permutation: every original item must appear exactly once, and, under the ideal random model, every possible ordering should have the same probability.

“Swap random pairs a few times” sounds plausible, but it does not by itself give a uniform permutation. Fisher–Yates solves the problem by finalizing one position at a time. At each step it selects uniformly from exactly the items that have not yet been placed. The modern in-place version uses one shrinking loop and constant auxiliary storage.

This lesson implements the backward version, traces a reproducible six-element example, proves its uniformity under explicit randomness assumptions, and counts all choice sequences on a tiny input to demonstrate how an incorrect range creates bias. You will also distinguish an ideal uniform shuffle from a deterministic replay produced by a fixed pseudorandom seed.

Core Concepts and Terminology

The input is an indexed mutable sequence $A$ of length $n$. The output occupies the same sequence and has exactly the same multiset of items. The sample programs use signed $32$-bit integers, but the shuffle does not inspect values or compare keys; it swaps positions, so the same algorithm works for records and references.

To state uniformity precisely, first imagine that every occurrence has its own label, even when two values look equal. There are $n!$ permutations of these labeled occurrences. A uniform shuffle assigns each probability $1/n!$. When values repeat with multiplicities $c_1,\ldots,c_d$, each distinct visible arrangement represents exactly $\prod_t c_t!$ labeled permutations, so it has probability

$$\frac{\prod_{t=1}^{d}c_t!}{n!}.$$

Thus equal values do not need special treatment. They do make position checks harder: attach identity labels when testing the distribution of individual occurrences.

The backward algorithm uses a boundary $i$. Immediately before processing $i$, positions $[0,i]$ remain active and positions $[i+1,n)$ are final. Here $[0,i]$ is inclusive at both ends, while $[i+1,n)$ excludes $n$. The active prefix has $i+1$ positions. Choose $j$ uniformly from that prefix, swap $A[i]$ and $A[j]$, and then decrease $i$. The choice $j=i$ is essential: leaving an item in place is a valid outcome.

Uniformity is a property of the whole distribution, not the appearance of a single output. For $n=3$, choosing only among cyclic rotations makes every item equally likely to occupy every position, yet reaches only three of the six permutations. Correct position marginals alone do not prove a uniform shuffle.

How Fisher-Yates Shuffle Works, Step by Step

Use zero-based indices and process $i=n-1,n-2,\ldots,1$. There is no need to process position $0$: once all other positions are fixed, its remaining item is determined.

1. Set the current active size to $m=i+1$.
2. Generate $j$ uniformly below $m$, giving $0\le j\le i$.
3. Swap $A[i]$ and $A[j]$. If their indices are equal, leave the array unchanged.
4. Treat position $i$ as final and continue with $i-1$.

The multiset is preserved by every exchange. The finalized suffix grows by one position per iteration, and later choices stay entirely in the active prefix. This supplies both progress and the structure needed for the probability proof.

flowchart TD
    A["Set i = array length - 1"] --> B{"i greater than 0?"}
    B -->|No| H["Return shuffled array and statistics"]
    B -->|Yes| C["Draw j uniformly below i + 1"]
    C --> D{"j equals i?"}
    D -->|Yes| F["Count the step; position i is final"]
    D -->|No| E["Swap A[i] with A[j]; count swap"]
    E --> F
    F --> G["Decrease i"]
    G --> B

Empty and singleton inputs require no draws and no swaps. The algorithm does not test whether the values are already ordered, whether they repeat, or whether a selected pair has equal values. A swap of distinct positions counts even if the visible values match.

To make the three implementations replay identically, they share a specified generator rather than unrelated language-library generators. Its state update is

$$s\leftarrow(16807s)\bmod2147483647,\qquad r=s-1,$$

with seed $1\le s\le2147483646$ and raw range $0\le r\lt B$, where $B=2147483646$. State multiplication uses $64$-bit arithmetic in C++ and Java. This generator is educational and deterministic; the uniformity proof assumes ideal choices, not that this fixed-seed generator supplies independent randomness.

For a bound $m$, set $L=B-(B\bmod m)$. Reject raw draws with $r\ge L$; otherwise return $r\bmod m$. The accepted interval contains exactly $L/m$ representatives of each residue. Consequently, this conversion avoids modulo bias when raw draws are independent and uniform. Rejection cannot remove correlations or add entropy to a deterministic generator.

For example, a raw range $\{0,\ldots,7\}$ reduced modulo $3$ gives residue counts $3,3,2$. Rejecting $6$ and $7$ leaves two representatives for every residue, so each accepted result has probability $1/3$. Do not replace the bounded-integer primitive by rounding a floating-point random value; endpoint and finite-precision rules can introduce other biases.

Worked Example with a Full Trace

Start with $A=[0,1,2,3,4,5]$ and seed $6$. There are five steps. The table records every state update, the corresponding raw value, the chosen index, and the complete array after the exchange. The active sizes are $6,5,4,3,2$; all five raw values fall below their respective acceptance limits, so no rejection occurs in this run.

At step $1$, $j=i=5$. The self-choice is accepted, position $5$ becomes final, and no physical swap is counted. At step $2$, indices $4$ and $3$ exchange, placing value $3$ in final position $4$. At step $3$, only indices $0$ through $3$ are eligible, so swapping $3$ with $1$ cannot disturb the suffix $[3,5]$.

The final result is $[4,2,0,1,3,5]$, with $5$ steps, $4$ exchanges of distinct positions, and $5$ raw draws. Position $0$ is determined after the loop. The remaining fixed point at position $5$ is valid: a correct shuffle is not required to move every item.

Under ideal independent uniform choices, this particular sequence of indices has probability

$$\frac16\cdot\frac15\cdot\frac14\cdot\frac13\cdot\frac12=\frac1{720}.$$

For labeled inputs, each final permutation corresponds to exactly one such choice sequence, so the displayed ordering has that same probability in the ideal model. With the fixed seed $6$, the program deterministically produces it; a deterministic replay does not itself have a $1/720$ success probability.

Implementation in Python, C++, and Java

Every panel contains a complete program. fisher_yates or fisherYates modifies its array in place and receives a generator object. Keeping that object outside the routine makes it possible to continue the same random stream across several shuffles. A fresh generator with the same seed, applied to a fresh copy of the same original array, reproduces the same result.

The portable contract accepts arrays of signed $32$-bit integers with length at most $2147483646$. Seeds must lie in $1$ through $2147483646$. The Python implementation can also swap other values, but its cross-language demonstration uses the same integer contract. Empty and singleton arrays preserve the generator state and report zero steps, swaps, and draws.

steps counts completed loop iterations, including self-choices. swaps counts exchanges of two different positions. draws is the number of generator state updates used by this call, including rejected values; it is measured relative to the generator's starting draw count, so reusing a generator does not mix the statistics of different calls. The final state is printed to make replay independently checkable.

class RNG:
    MOD = 2147483647
    RANGE = MOD - 1

    def __init__(self, seed):
        if not isinstance(seed, int) or not 1 <= seed < self.MOD:
            raise ValueError("seed must be in 1..2147483646")
        self.state = seed
        self.draws = 0

    def below(self, bound):
        if not 1 <= bound <= self.RANGE:
            raise ValueError("invalid random bound")
        limit = self.RANGE - self.RANGE % bound
        while True:
            self.state = (16807 * self.state) % self.MOD
            self.draws += 1
            r = self.state - 1
            if r < limit:
                return r % bound


class Stats:
    def __init__(self):
        self.steps = self.swaps = self.draws = 0


def fisher_yates(a, rng):
    if len(a) > RNG.RANGE:
        raise ValueError("array exceeds generator range")
    stats = Stats()
    start_draws = rng.draws
    for i in range(len(a) - 1, 0, -1):
        j = rng.below(i + 1)
        stats.steps += 1
        if i != j:
            a[i], a[j] = a[j], a[i]
            stats.swaps += 1
    stats.draws = rng.draws - start_draws
    return stats


def main():
    original = [0, 1, 2, 3, 4, 5]
    a = original.copy()
    rng = RNG(6)
    stats = fisher_yates(a, rng)
    replay = original.copy()
    fisher_yates(replay, RNG(6))
    print("shuffled = [" + ", ".join(map(str, a)) + "]")
    print(f"steps={stats.steps}, swaps={stats.swaps}, draws={stats.draws}")
    print(f"final state = {rng.state}")
    print("multiset check = " + ("PASS" if sorted(a) == sorted(original) else "FAIL"))
    print("replay check = " + ("PASS" if replay == a else "FAIL"))


if __name__ == "__main__":
    main()

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <vector>
using Array = std::vector<int>;

struct RNG {
    static constexpr std::int64_t MOD = 2147483647;
    static constexpr std::int64_t RANGE = MOD - 1;
    std::int64_t state, draws = 0;
    explicit RNG(std::int64_t seed) : state(seed) {
        if (seed < 1 || seed >= MOD) throw std::invalid_argument("invalid seed");
    }
    int below(int bound) {
        if (bound < 1 || bound > RANGE) throw std::invalid_argument("invalid random bound");
        std::int64_t limit = RANGE - RANGE % bound;
        for (;;) {
            state = (16807 * state) % MOD;
            ++draws;
            std::int64_t r = state - 1;
            if (r < limit) return static_cast<int>(r % bound);
        }
    }
};
struct Stats { std::int64_t steps = 0, swaps = 0, draws = 0; };

Stats fisher_yates(Array& a, RNG& rng) {
    if (a.size() > static_cast<std::size_t>(RNG::RANGE))
        throw std::invalid_argument("array exceeds generator range");
    Stats stats;
    std::int64_t start_draws = rng.draws;
    for (int i = static_cast<int>(a.size()) - 1; i > 0; --i) {
        int j = rng.below(i + 1);
        ++stats.steps;
        if (i != j) { std::swap(a[i], a[j]); ++stats.swaps; }
    }
    stats.draws = rng.draws - start_draws;
    return stats;
}

int main() {
    Array original = {0, 1, 2, 3, 4, 5}, a = original;
    RNG rng(6); Stats stats = fisher_yates(a, rng);
    Array replay = original; RNG replay_rng(6); fisher_yates(replay, replay_rng);
    std::cout << "shuffled = [";
    for (std::size_t i = 0; i < a.size(); ++i) { if (i) std::cout << ", "; std::cout << a[i]; }
    std::cout << "]\nsteps=" << stats.steps << ", swaps=" << stats.swaps << ", draws=" << stats.draws << '\n';
    std::cout << "final state = " << rng.state << '\n';
    Array check = a; std::sort(check.begin(), check.end());
    Array expected = original; std::sort(expected.begin(), expected.end());
    std::cout << "multiset check = " << (check == expected ? "PASS" : "FAIL") << '\n';
    std::cout << "replay check = " << (replay == a ? "PASS" : "FAIL") << '\n';
    return 0;
}

import java.util.Arrays;

public class Main {
    static class RNG {
        static final long MOD = 2147483647L, RANGE = MOD - 1;
        long state, draws;
        RNG(long seed) {
            if (seed < 1 || seed >= MOD) throw new IllegalArgumentException("invalid seed");
            state = seed;
        }
        int below(int bound) {
            if (bound < 1 || bound > RANGE) throw new IllegalArgumentException("invalid random bound");
            long limit = RANGE - RANGE % bound;
            while (true) {
                state = (16807L * state) % MOD; ++draws;
                long r = state - 1;
                if (r < limit) return (int)(r % bound);
            }
        }
    }
    static class Stats { long steps, swaps, draws; }

    static Stats fisherYates(int[] a, RNG rng) {
        if (a.length > RNG.RANGE) throw new IllegalArgumentException("array exceeds generator range");
        Stats stats = new Stats(); long startDraws = rng.draws;
        for (int i = a.length - 1; i > 0; --i) {
            int j = rng.below(i + 1); ++stats.steps;
            if (i != j) { int t = a[i]; a[i] = a[j]; a[j] = t; ++stats.swaps; }
        }
        stats.draws = rng.draws - startDraws;
        return stats;
    }

    public static void main(String[] args) {
        int[] original = {0, 1, 2, 3, 4, 5}, a = original.clone();
        RNG rng = new RNG(6); Stats stats = fisherYates(a, rng);
        int[] replay = original.clone(); fisherYates(replay, new RNG(6));
        System.out.println("shuffled = " + Arrays.toString(a));
        System.out.println("steps=" + stats.steps + ", swaps=" + stats.swaps + ", draws=" + stats.draws);
        System.out.println("final state = " + rng.state);
        int[] check = a.clone(), expected = original.clone(); Arrays.sort(check); Arrays.sort(expected);
        System.out.println("multiset check = " + (Arrays.equals(check, expected) ? "PASS" : "FAIL"));
        System.out.println("replay check = " + (Arrays.equals(replay, a) ? "PASS" : "FAIL"));
    }
}

Run Python 3 directly. Compile C++ with g++ -std=c++14 -O2 main.cpp -o shuffle, or compile Java 17 or later with javac Main.java and run java Main. Each program prints exactly these five lines:

• shuffled = [4, 2, 0, 1, 3, 5]
• steps=5, swaps=4, draws=5
• final state = 422202639
• multiset check = PASS
• replay check = PASS

The multiset check uses sorted copies, and the replay check starts from a fresh copy of the original input. These are useful integrity checks; neither proves uniformity. Do not compare a shuffled array with a sorted array expecting equality, and do not expect a second call on an already-shuffled array to reproduce the first result merely because the seed was reset.

The sample's sorting-based verification takes $O(n\log n)$ time and its copies take $O(n)$ storage. Those costs belong to the demonstration harness, not to the core shuffle. The shuffle itself performs no key comparisons and does not allocate an auxiliary array.

Complexity, Correctness, and Invariants

For $n\ge2$, the algorithm performs exactly $n-1$ bounded choices and exactly $n-1$ loop steps, independent of the data or the choices. It performs at most $n-1$ physical swaps, with a minimum of zero if every draw is a self-choice. Thus its array work is $\Theta(n)$ in the best, average, and worst case, assuming a constant-cost bounded-random primitive. It uses $O(1)$ auxiliary space with no recursion. Empty and singleton cases take constant time.

Actual random-range conversion may retry. If $D$ raw draws are used, these implementations take $\Theta(n+D)$ time. Under independent uniform raw draws, the rejection sampler accepts with probability greater than $1/2$, so expected $D$ is less than $2(n-1)$ for $n\ge2$ and expected total time remains $\Theta(n)$. An ideal rejection stream has no finite deterministic upper bound on its number of retries; the fixed-seed finite generator has a different deterministic behavior. Do not describe its variable raw draw count as exactly $n-1$ in every run.

The random information required for an ideal uniform labeled permutation is $\log_2(n!)=\Theta(n\log n)$ bits. This is compatible with linear word-level work when random integers and array operations are treated as word operations. A deterministic generator does not create new entropy at every state update.

The deterministic invariant is simple: the array always contains exactly the original occurrences, and the finalized suffix is never changed again. It holds because each step swaps only positions at most $i$. The boundary decreases on every iteration, so the loop terminates.

For the probabilistic invariant, assume every choice is uniform conditional on the entire preceding history. Before processing $i$, the finalized suffix is a uniform ordered selection of $n-i-1$ distinct labeled occurrences. Each remaining occurrence occupies exactly one of the $i+1$ active positions. Choosing $j$ uniformly selects each remaining occurrence with probability $1/(i+1)$, extending the suffix by one uniformly chosen unused occurrence. No assumption that the active prefix is already randomly ordered is needed.

Fix any target labeled permutation $\pi$. The final position must receive $\pi_{n-1}$, then the next position must receive $\pi_{n-2}$ from the remaining occurrences, and so on. Therefore

$$\Pr(A_{\mathrm{final}}=\pi)=\frac1n\cdot\frac1{n-1}\cdots\frac12\cdot1=\frac1{n!}.$$

Equivalently, the numbers of choices are $n,n-1,\ldots,2$, giving $n!$ equally likely schedules, and there is a bijection between schedules and labeled output permutations. Given a target permutation, the desired occurrence for position $i$ identifies exactly one eligible index at that step. Merely counting $n!$ schedules would not suffice without this one-to-one correspondence.

Self-choices are a normal part of this proof. At step $i$, their probability is $1/(i+1)$. For $n\ge1$, the expected number of skipped self-exchanges is $H_n-1$, where $H_n=\sum_{t=1}^{n}1/t$. Hence the expected number of distinct-position swaps is $n-H_n$ under the ideal model. This is a different quantity from the number of final fixed points: an item can move several times and later return to its original position.

For a uniform permutation with $n\ge1$, each labeled occurrence has probability $1/n$ of being fixed, so the expected total number of fixed points is $1$. The original ordering itself occurs with probability $1/n!$; rejecting it and reshuffling changes the target distribution. For $n=0$, there is one empty permutation, with probability $1$, consistent with $0!=1$.

Variants, Pitfalls, and Optimizations

The key implementation decision is the shrinking index range. Consider a buggy backward version on $[0,1,2]$ that processes $i=2$ and $i=1$ but chooses $j$ from all three positions both times. Its nine equally likely schedules cannot split evenly among six permutations. In exact enumeration, outputs $012,021,201$ occur twice each, while $102,120,210$ occur once each. Correct Fisher–Yates has six schedules and produces every permutation exactly once.

Other mistakes and useful variants deserve separate treatment:

• Include the self-choice. Drawing below $i$ instead of below $i+1$ changes the algorithm to Sattolo's cyclic-permutation construction. For $n\gt1$, it produces one-cycle permutations rather than all permutations. Although such permutations have no fixed points, this is not uniform sampling from all derangements either.
• Match direction to the active region. Backward Fisher–Yates chooses from $[0,i]$ and freezes a suffix. A forward version chooses from $[i,n-1]$ and freezes a prefix. Changing the loop direction without changing the sampling interval can destroy the proof.
• Sample a subset without fully shuffling. Performing only the first $k$ backward steps selects a uniform ordered sample in the last $k$ positions. Read in the actual selection order, from the end backward, or reverse that order consistently; both give a uniform ordered sample. For all $n$ items the last remaining item is forced, so the final singleton draw can be omitted.
• Use inside-out construction for a separate output. When inserting input item number $i$, choose $j$ uniformly from $[0,i]$. If $j\ne i$, move the old output at $j$ to the new position $i$; then write the new item at $j$. The condition avoids reading the new slot before it exists. This method needs growing output storage.
• Treat finite-key sorting carefully. Assigning random keys and sorting is slower, and tied keys resolved by original order generally bias the result. A random comparator is worse: it can violate the sorting algorithm's ordering requirements and is not a shuffle algorithm.
• Manage generator state explicitly. Recreating a generator with the same seed before every choice repeatedly uses the first raw value. Sharing mutable state across concurrent tasks can also make replay depend on scheduling; use a documented stream-management strategy.

There is a sharp distinction between an exact mathematical shuffle and a finite seeded implementation. This program has only $B=2147483646$ possible starting states. For a fixed initial array, each state determines one complete output, so at most $B$ distinct permutations can be reached by varying the seed. Already $13!=6227020800\gt B$, making full coverage impossible for thirteen distinct items with this generator. Having fewer permutations than states would still not prove equal probabilities or independence.

Choose an appropriate random source for the application. A simple generator is convenient for teaching, replay, and some controlled experiments; unpredictable dealing or security-sensitive randomization needs a suitable cryptographic source and a correct bounded-integer API. The same Fisher–Yates swap logic can be used with a different source. Its sampling interface and state policy are part of the algorithm's contract.

Practice Problems and Real-World Use

Use three complementary kinds of validation. First, check length and multiplicities after every shuffle, including repeated values and extreme integers. Second, enumerate all legal choice schedules for small labeled arrays using a scripted choice source; each permutation must occur once. Third, test the random-range conversion separately, including rejected raw values. Seed replay checks portability, while statistical experiments are diagnostics rather than proofs.

For larger experiments, count complete permutations when the state space is small enough, and examine pairwise order or joint-position frequencies as well as single-position counts. A statistical test can fail to detect a biased implementation, and a correct random process can occasionally produce an unusual sample. The proof supplies the distributional guarantee under its assumptions; tests check that the implementation follows the specified operations.

The NIST Dictionary of Algorithms and Data Structures entry describes the shuffle and the limitations of finite pseudorandom generators. The Python random-module documentation documents in-place shuffling, sampling without replacement, state management, and its generator's limitations. Use the proof's conditional-uniformity assumption when assessing an alternative random source, rather than treating any function named “random” as interchangeable.