A log tailer wants 5 random request ids from a file that is still being written. n is not known. Loading the whole file to Fisher-Yates is not a pass over a stream. Picking with nextDouble() < k / soFar without the right i biases early or late lines.

Algorithm R: fill a reservoir of k, then for each subsequent item number i (i = k+1, k+2, …), replace a random reservoir slot with probability k/i. When the stream ends, every item that appeared had equal probability k/n of sitting in the reservoir (for n ≥ k).

This post is that pass. Known-n shuffle is Fisher-Yates. Catalog: Algorithms Roadmap. It is not a reason to store the stream, not weighted sampling (Efraimidis–Spirakis is a different procedure), and not a crypto lottery.

Why “random 5 of the first 5, then maybe swap” is fair

After i items, each of those i should be in the reservoir with probability k/i (when i ≥ k). Item i+1 enters with probability k/(i+1). Each occupant is evicted with probability 1/k given a replacement, so it stays with 1 - 1/(i+1) = i/(i+1), and

k/i · i/(i+1) = k/(i+1)

The invariant holds. You never need n until you stop.

static <T> List<T> reservoir(Iterator<T> stream, int k, Random r) {
    List<T> res = new ArrayList<>(k);
    int i = 0;
    while (stream.hasNext()) {
        T item = stream.next();
        i++;
        if (i <= k) {
            res.add(item);
        } else {
            int j = r.nextInt(i); // 0..i-1
            if (j < k) {
                res.set(j, item);
            }
        }
    }
    return res;
}

i is 1-based count. nextInt(i) is 0 .. i-1. Probability k/i that j < k. Empty stream: empty list. Stream shorter than k: return what you got (the spec should say whether to throw).

Note: Random.nextInt(i) requires i > 0. After the first item, i ≥ 1. For k = 0, return empty and skip the loop policy.

Application code: if the source is a List you already hold, Fisher-Yates partial shuffle is simpler. Reservoir is the online contract.

One sample (k = 1)

Probability the current item replaces the winner is 1/i. Equivalent: if (r.nextInt(i) == 0) pick = item. That is the “random element of an unknown-length iterator” interview.

When not to use reservoir

  • n known, array in RAM. Fisher-Yates partial shuffle.
  • Weighted items. Exponential-jump / keyed sampling; not Algorithm R.
  • You needed every item with probability p, independently. That is Bernoulli, not a fixed k.

Cheat sheet

Job:       uniform k-sample from a stream; n unknown
Fill:      first k items
Then:      item i (1-based) enters with P = k/i, replacing a random slot
Invariant: after i items, each has P = k/i in the reservoir (i≥k)
k=1:       replace winner when nextInt(i)==0
JDK:       none; Iterator + Random; shuffle if you already have a List
Not this:  Fisher-Yates on a known array; weighted reservoir

Do:

  • Count i from 1 as items arrive.
  • Use nextInt(i) < k for the replacement test.
  • Prefer partial Fisher-Yates when the collection is already loaded.

Don’t:

  • Use a fixed probability 0.1 on every line and call it a sample of 5.
  • Load the stream to shuffle “because Fisher-Yates is unbiased.”
  • Forget the short-stream case (n < k).

Wrap-up

Reservoir sampling keeps k slots and, for each new item i, gives it probability k/i to enter. You do not know n until the iterator ends. When n is known and in memory, shuffle instead.

Wave 5 of this series stops here: strings, then numbers, then sampling. DP and greedy start at knapsack.

Next optional step in the series Pick or skip when each item exists once — 0/1 knapsack starts Wave 6. 0/1 Knapsack: Pick or Skip When Each Item Exists Once