Introduction

Picking a random integer from 0 through N - 1 while excluding a given list is easy to state and surprisingly easy to get wrong. The best solution depends on how many values are excluded and whether you need one random pick or many repeated picks.

The simple solution for small exclusion lists

If the blocked list is small compared with N, rejection sampling is perfectly fine. Generate a random number, check whether it is excluded, and try again if necessary.

1import random
2
3def pick_not_in_list(n, blocked):
4    blocked = set(blocked)
5    if len(blocked) >= n:
6        raise ValueError("no valid numbers left")
7
8    while True:
9        value = random.randrange(n)
10        if value not in blocked:
11            return value
12
13print(pick_not_in_list(10, [2, 5, 7]))

This is simple and correct. The problem is performance when the excluded set becomes dense. If N is 1_000_000 and 999_990 values are blocked, this loop wastes a lot of time.

The better solution for repeated picks

If you need many random picks, preprocess the blocked values once and convert the problem into a random pick over a smaller valid range. A standard trick is to map blocked numbers in the low part of the range to allowed numbers in the high part.

Suppose there are k blocked numbers. Then there are N - k valid outputs. You can pick a random integer from 0 through N - k - 1. If that pick is not blocked, return it directly. If it is blocked, remap it to a valid high-end number.

1import random
2
3class RandomExcluded:
4    def __init__(self, n, blocked):
5        blocked = set(blocked)
6        if len(blocked) >= n:
7            raise ValueError("no valid numbers left")
8
9        self.limit = n - len(blocked)
10        self.remap = {}
11
12        high_candidates = iter(
13            x for x in range(self.limit, n) if x not in blocked
14        )
15
16        for x in blocked:
17            if x < self.limit:
18                self.remap[x] = next(high_candidates)
19
20    def pick(self):
21        x = random.randrange(self.limit)
22        return self.remap.get(x, x)
23
24picker = RandomExcluded(10, [2, 5, 7])
25samples = [picker.pick() for _ in range(10)]
26print(samples)

This gives uniform results without repeated retries. The preprocessing cost is paid once, then each pick is effectively constant time.

Choosing the right approach

Use rejection sampling when:

• the blocked list is small
• you only need one or a few picks
• simplicity matters more than worst-case efficiency

Use preprocessing when:

• the blocked list is large
• you need many picks from the same exclusion set
• predictable performance matters

There is also a middle-ground approach: build an explicit list of allowed values and use random.choice. That is very readable, but it stores every valid number and can become memory-heavy when N is large.

1import random
2
3def pick_with_allowed_list(n, blocked):
4    blocked = set(blocked)
5    allowed = [x for x in range(n) if x not in blocked]
6    if not allowed:
7        raise ValueError("no valid numbers left")
8    return random.choice(allowed)

Why uniformity matters

A correct algorithm should give every allowed value the same probability. Some ad hoc approaches accidentally bias the result by compressing ranges unevenly or by retrying from a non-uniform source. The mapping technique above stays uniform because it selects evenly from exactly the number of valid outputs.

That detail matters in simulations, load balancing, randomized testing, and any code where subtle bias can accumulate over time.

Common Pitfalls

• Using a list for membership tests inside a retry loop. Convert it to a set first.
• Forgetting the edge case where every value is excluded.
• Using rejection sampling when the valid range is tiny, which can make runtime unpredictable.
• Building a full allowed list for very large N when a mapping-based solution would be cheaper.
• Returning a remapped value with a biased formula instead of a true one-to-one mapping.

Summary

• Rejection sampling is the easiest answer when the blocked list is small.
• For repeated picks or dense exclusions, preprocess the blocked values and remap low blocked values to valid high values.
• Convert the exclusion list to a set for fast lookups.
• Always handle the case where no valid number exists.
• Pick the approach based on exclusion density and how often you need to sample.