Random shuffles and sampling

The Fisher–Yates shuffle puts n items in random order so that each of the n! orders is equally likely: walk from the last position down to the second, and swap the item there with one at a uniformly random position at or before it. Random shuffles, samples and weighted picks come up in interviews because the obvious code is often quietly unfair. Sampling has two more classics: reservoir sampling keeps k items from a stream whose length nobody knows, and a weighted pick returns index i with probability proportional to its weight. Rejection sampling turns one fair generator into another by discarding the draws that would make the result uneven. Two popular shortcuts, sorting with a random comparator and swapping each item with any position at all, give random shuffles that are measurably biased.

Three draws for a college fest

Problem A: shuffle the entries. A college fest’s lucky draw lists n ≤ 10⁶ registration numbers. Using randbelow(m), which returns a uniform integer from 0 to m − 1, put the list in random order in place, so that each of the n! orders has the same chance.

Problem B: sampling a stream. Tickets are scanned at the gate one by one, and nobody knows how many will come. Keep k = 5 of them in memory so that, when the gate closes, every scanned ticket is among the five with the same probability.

Problem C: pick a stall by weight. Stall i holds wᵢ prize tokens, 0 ≤ wᵢ ≤ 10⁹, for n ≤ 10⁵ stalls. Build a picker once, then answer 10⁵ picks, each returning stall i with probability wᵢ / W, where W is the total. With the weights 1, 3, 0 and 6, stall 3 wins 60 % of the picks and stall 2 never wins.

The brute force, and where it breaks

Problem A can list every order and pick one: 24 orders for four finalists, but 20! has 19 digits and 10⁶! has 5,565,709. The Fisher–Yates shuffle needs only n − 1 random choices instead. Problem B can store every ticket and sample at the end, with memory for the whole stream, while reservoir sampling holds only the k tickets it may return. Problem C can expand every stall into one copy per token, about 5 × 10¹² copies in the run, or scan the running totals for every pick, about 5 × 10⁹ steps for 10⁵ picks among 10⁵ stalls.

# The obvious approach to each of the three problems, and what it costs at the stated sizes.
import itertools
import math
import random

rng = random.Random(2026)

# Problem A: list every order and pick one of them uniformly.
finalists = ["R101", "R102", "R103", "R104"]
orders = list(itertools.permutations(finalists))
print(f"4 finalists: {len(orders)} orders, one picked: {list(orders[rng.randrange(len(orders))])}")
for n in (10, 20, 1_000_000):
    digits = len(str(math.factorial(n))) if n < 1000 else int(math.lgamma(n + 1) / math.log(10)) + 1
    print(f"{n:,} entries: {n}! has {digits:,} digits")

# Problem B: keep the whole stream, then sample k = 5 at the end.
kept = [f"T{i:07d}" for i in range(200_000)]  # 200,000 scanned tickets held in memory
winners = rng.sample(kept, 5)
print(f"stream of {len(kept):,} tickets stored to pick {len(winners)} winners")

# Problem C: a linear scan of the running totals for every pick.
weights = [rng.randint(0, 10**9) for _ in range(10_000)]
total = sum(weights)
steps = 0
for _ in range(1_000):
    target = rng.random() * total
    running = 0
    for i, w in enumerate(weights):
        steps += 1
        running += w
        if running > target:
            break
print(f"1,000 picks among 10,000 stalls: {steps:,} steps, about {steps // 1000:,} per pick")
print(f"expanding every stall into one copy per unit of weight: {total:,} copies")

4 finalists: 24 orders, one picked: ['R101', 'R103', 'R104', 'R102']
10 entries: 10! has 7 digits
20 entries: 20! has 19 digits
1,000,000 entries: 1000000! has 5,565,709 digits
stream of 200,000 tickets stored to pick 5 winners
1,000 picks among 10,000 stalls: 4,953,653 steps, about 4,953 per pick
expanding every stall into one copy per unit of weight: 4,944,655,828,737 copies

What to notice

• An order is uniform when each position, filled from the end, gets a uniform choice among the items not yet placed.
• A stream item only needs the right chance of entering when it arrives, k / i for the i-th item, without knowing what comes later.
• The running totals cut [0, W) into one interval per stall, so a uniform point lands in stall i’s interval with probability wᵢ / W, and finding the interval is a binary search.

Fisher–Yates, and why each order has probability 1/n! Pro: opens with a Pro, Premium or Ultimate pass