Skip to main content

Drawing Without Replacement: Elimination and Exclusions

A fair draw is a pool plus rules, not one random number — how no-repeats batches, elimination mode, and interval-based exclusions work in the browser.

Updated 8 min readMarkdown

Drawing Without Replacement: Elimination and Exclusions

Yesterday's post was about the random source: why Math.random() is the wrong tool for a giveaway draw, and why Web Crypto with rejection sampling is the right one. Today is about everything that happens after the random source — the part that actually breaks real draws. A fair draw is not one random number. It is a pool, a set of rules about that pool, and a way to draw from it repeatedly without ever picking the same entry twice.

Disclosure: I built the tool this post uses as its running example — the Random Number Generator at toolkitloop.com. The code below is mine, written to explain the mechanics; the tool's own behaviour is described from its public page, including its stated limits.

The problem: "pick one" is easy, "pick many, never twice" is not

Drawing one number from 1 to N is a solved problem: one uniform integer, done. Drawing k unique numbers from 1 to N is where implementations start to diverge, and the divergence matters. Three common approaches exist, and each has a failure mode.

Re-roll on collision. Draw, check if the number was already drawn, re-draw if it was. Simple, correct in distribution, and fine for small k. But as k approaches N, collisions pile up: drawing the last few unique numbers from a nearly exhausted pool means re-rolling most attempts. For k close to N it degrades badly.

Shuffle then take. Build the full list 1..N, shuffle it (Fisher–Yates), take the first k. Clean and uniform, but it costs O(N) memory and time up front. For N = 10,000 that is trivial. For N = 10^12 it is impossible — you cannot materialise a trillion-entry array.

Interval sampling. Represent the allowed values as a set of intervals, pick a random position in the total count, and map it back to a value. This is what the ToolkitLoop tool does: it "calculates allowed intervals instead of building a huge array, so large integer ranges remain practical." The cost stays proportional to the number of intervals, not the size of the range.

Which one should you use? It depends on N, on k, and on whether the pool changes between draws. That is the real design question, and it splits into three features: no-repeats batches, elimination mode, and exclusions.

No repeats: one batch, one contract

"No repeats" in the tool means this: within one multi-number result, every value is unique. The contract is scoped to a single result. Generate 3 winners from 1–200 and you get 3 different numbers. Generate again and a number from the first result can reappear, because the second result is a fresh draw from the full pool.

This scoping surprises people, but it is the honest one. A batch draw is a single sampling event; the tool makes no promise across events. If you need three winners, get them in one result. If you run three separate single draws, you have run three independent events, and duplicates are not a bug — they are the expected behaviour of independent draws.

The implementation question for a batch is the classic one: shuffle-then-take is fine when N is small, and interval sampling is what you want when N is large. Either way, the invariant to test is simple: run the batch 10,000 times, count how often any value repeats inside a result. The answer must be zero, every time.

Elimination mode: stateful draws, one at a time

Elimination mode is a different beast: it is stateful. Each draw removes the drawn number from the pool, and the pool persists until you reset it. That is what "draws one number at a time and removes earlier draws from the current pool until you reset it" means in practice.

State changes the testing story completely. A stateless batch can be tested by running it in a loop. A stateful draw has to be tested as a sequence: draw until the pool is empty, and verify that every value from 1 to N appeared exactly once. If any value appears twice, or any value never appears, the elimination logic is broken — probably a stale index, or a removal that happened after the next draw was already computed.

There is also a UX trap: the reset. Elimination mode needs an explicit reset, and the reset has to be obvious, because a user who forgets to reset will draw from a half-empty pool and get a result that looks wrong. The tool's reset is the boundary between one event and the next; without it, two separate giveaways silently share one pool.

When would you choose elimination over a batch? When the draws are sequential and public: a live stream, a classroom calling on students one by one, a bingo-style round. The audience watches the pool shrink. A batch is better when you need a winner list and nobody is watching the process unfold.

Exclusions: intervals, not lists

Exclusions are where the interval representation earns its keep. Excluding a single number is easy in any implementation. Excluding a range — say, entries 198–200 arrived late — is where list-based approaches start to hurt: you filter the list, rebuild it, and re-index. With intervals, an exclusion just splits an interval in two.

Consider a pool of 1–200 with exclusions 12, 13, and 198–200. As intervals, that is [1–11], [14–197]. Two intervals, total size 195. Drawing means picking a random position in 0..194 and mapping it: positions 0–10 map to 1–11, positions 11–194 map to 14–197. No array of 195 entries, no filtering pass, and the same code handles a pool of 1–10^12 with a handful of exclusions.

The edge cases to get right:

  • Exclusion covering the whole range. If the user excludes everything, there is nothing to draw. The tool must refuse with a clear message, not return a number or hang.
  • Adjacent exclusions. Excluding 12–13 and 14–15 should merge into one excluded interval, 12–15. Failing to merge is harmless but wasteful; failing to handle the boundary is how off-by-one errors sneak in.
  • Exclusion endpoints. Excluding "198–200" from a pool of 1–200 must leave 197 drawable and 198 not. Test both sides of every boundary.
  • Unique count vs. pool size. The maximum number of unique values you can generate at once is the size of the pool after exclusions — for example, 100 unique values from 1 to 100. Ask for more and the tool asks you to expand the range. That check has to use the post-exclusion pool size, not the raw range.

The sampling core: rejection sampling without modulo bias

Underneath all of this sits the random source from yesterday's post, and it is worth showing the shape of it:

// Uniform integer in [min, max] from Web Crypto, no modulo bias.
function secureRandomInt(min, max) {
  const range = max - min + 1;
  const maxUint32 = 0xFFFFFFFF;
  // Largest multiple of range that fits in a uint32: reject above it.
  const limit = Math.floor((maxUint32 + 1) / range) * range - 1;
  const buf = new Uint32Array(1);
  let value;
  do {
    crypto.getRandomValues(buf);
    value = buf[0];
  } while (value > limit);
  return min + (value % range);
}

The rejection step is the whole trick: values above the largest multiple of the range are discarded, so every residue class modulo the range is equally likely. The expected number of rejections is tiny — at most one extra draw on average in the worst case — so the loop is cheap. Then the interval mapping turns that uniform integer into a uniform pick from the allowed set: pick a position, walk the intervals, return the value.

Put together, the pipeline is: exclusions carve the pool into intervals, the interval total defines the draw space, rejection sampling picks a uniform position, and the mode (batch vs. elimination) decides whether the pool changes after the pick. Each layer is independently testable, which is exactly how you want a draw tool to be built.

What this does not give you

Two honest limits, both stated on the tool's page. First, a browser draw is not an independently audited or legally verifiable draw service. If the stakes involve regulation, cash prizes with legal requirements, or a dispute that might end up in front of a third party, use a certified draw service. Second, everything runs in the current browser session: the range, exclusions, and results are not sent anywhere, which is good for privacy, but it also means the record of the draw is whatever you write down. Screenshot the result, copy the numbers into your announcement, and publish the rules alongside them. The tool gives you a fair draw; the paper trail is your job.

The question I keep coming back to

Most draw tools get the random number right and the pool management wrong — or they get the pool right and hide it behind an interface that never shows you the exclusions. If you have built or used a draw tool, what broke first: the randomness, the no-replacement logic, or the part where someone had to trust the result? I am curious which layer you would test first, and why.

Try the tool: https://toolkitloop.com/random-number-generator — free, no signup, everything runs in your browser.

About the author

  • Founder of ToolkitLoop (toolkitloop.com) — 30 free online tools that run 100% in your browser. No sign-ups, no uploads, private by design.

No comments yet. Be the first to comment.