Generate Unique Random Integers Without Bias
Picking N unique random integers from a range sounds simple, but the right algorithm depends on how N compares to the range size. Retry-into-a-Set is fine when N is small relative to the population, but as N approaches the range size retries dominate and a partial Fisher-Yates shuffle becomes the right answer. For streams of unknown size, reservoir sampling is the only option that gives uniform probability in a single pass.
505 views
12
// Pick n distinct integers in [0, max). Retry on collision.
const pickUnique = (n, max) => {
if (n > max) throw new Error('cannot pick more uniques than the range size');
const picked = new Set();
while (picked.size < n) {
picked.add(Math.floor(Math.random() * max));
}
return [...picked];
};
console.log(pickUnique(5, 100)); // 5 unique integers in [0, 99]
console.log(pickUnique(10, 100)); // 10 unique integers
// Verify uniqueness in the output:
const sample = pickUnique(20, 1000);
console.log(sample.length === new Set(sample).size); // trueWhen the population is much larger than the count you need (say n / max < 0.5), each random draw is almost guaranteed to be new. The expected number of retries to fill the Set is n + small constant, so this is O(n) in practice and the code stays readable. Throw early if the caller asks for more uniques than the range allows, otherwise the loop never terminates. This is the right default for picking 5 of 100, 50 of 10000, or any case where you are sampling sparsely from a large pool.
// When n is close to max, retries dominate. Build the full population, shuffle
// only the first n positions, return the first n. O(n), unbiased.
const pickUniqueShuffle = (n, max) => {
if (n > max) throw new Error('cannot pick more uniques than the range size');
const pool = Array.from({ length: max }, (_, i) => i);
for (let i = 0; i < n; i++) {
// Pick a random index in [i, max).
const j = i + Math.floor(Math.random() * (max - i));
[pool[i], pool[j]] = [pool[j], pool[i]];
}
return pool.slice(0, n);
};
console.log(pickUniqueShuffle(95, 100)); // 95 unique integers in [0, 99]
console.log(pickUniqueShuffle(99, 100)); // 99 unique integers (degenerate but works)
// Sanity check: every output is unique.
const sample2 = pickUniqueShuffle(80, 100);
console.log(sample2.length === new Set(sample2).size); // trueThe retry approach degrades when n approaches max: at n = max - 1, the last draw collides on every value already picked except one, costing roughly max retries on its own. The partial Fisher-Yates fix builds the full [0..max) array once, then shuffles only the first n positions and returns that prefix. Each iteration picks a random index in [i, max) and swaps; the result is a uniform random sample without any retry loop. Memory is O(max), time is O(n), and the algorithm produces every n-permutation with equal probability. Use this when n / max > 0.5 or when you cannot tolerate the variance in retry counts.
// Pick n uniformly random items from a stream whose total length is unknown
// at the start. Algorithm R, the textbook reservoir sampler.
const reservoirSample = (iter, n) => {
const reservoir = [];
let i = 0;
for (const item of iter) {
if (i < n) {
reservoir.push(item);
} else {
// Replace a random reservoir slot with probability n / (i + 1).
const j = Math.floor(Math.random() * (i + 1));
if (j < n) reservoir[j] = item;
}
i++;
}
return reservoir;
};
// Sample 5 items from a stream of 1000.
function* range(start, end) {
for (let k = start; k < end; k++) yield k;
}
const sampled = reservoirSample(range(0, 1000), 5);
console.log(sampled.length); // 5
console.log(sampled.every((v) => v >= 0 && v < 1000)); // trueReservoir sampling solves a different problem: pick n uniformly random items from a stream whose total length is not known until you finish iterating. You cannot store everything, you cannot index randomly, and you cannot revisit. Algorithm R fills the first n items into the reservoir, then for each subsequent item at position i (0-indexed) it picks a random slot in [0, i]; if that slot is < n, the new item replaces the reservoir slot. The math works out so every item ends up in the reservoir with probability n / total. Use this for log lines, paginated APIs, or any source where the total count is unknown or huge.