Generate random number but exclude multiple ranges without looping

Question

I'm looking for a mathematical approach for generating a random number between [a, b) with holes at [c, d), [e, f), [g, h) and so on where a < b and the ranges are within the bounds.

I've found numerous examples here on how to do make the algorithm work if there is one missing range but can't seem to find a space/time efficient approach that generalizes to multiple ranges. What I mean here is that both:

a. A list of all possible ranges and choosing from that list: doesn't work well for large ranges

b. Generating a random number and checking if it is one of the ranges, otherwise trying again: unbounded terms of runtime

Some salient test cases might be:

generate_random(start=0, end=100, exclude: [(2,50),(51, 100)])
generate_random(start=0, end=1e16, exclude: [(1e6,1e7),(1e3, 1e4)])

Here are some of the examples I have found:

• Generating a random number between multiple ranges

• Can Python generate a random number that excludes a set of numbers, without using recursion?

Answer 1

So you want to pick any one of a..c-1, d..e-1, ..., x..b-1 ?

So N = (c-a) + (e-d) + ... + (b - x). Select random r in 0..N-1. If r < c, you are done. Set r = r + d, if r < e, you are done...

• Dialecticus: If there are M ranges (where M is big) then we have a linear search (O(M)) to determine the offset for r. Special binary search by ranges would be faster (O(log M)).
• Adithya: Ah this makes a bit more sense, okay, now what about if I want to expand this to two dimensions. (ie, my original goal which is to find unoccupied bounding boxes in an image of a preset width and height) The issue that will arise here is that I have more restrictions in that if I cannot make box of a specific height in a particular range that should be excluded as well.
• Chris Hall: @Adithya: I'm guessing you mean that for each range a..c-1, d..e-1, etc. for x, you have a distinct set of ranges for y ? In the process of selecting x you need to note which range x is in -- say rx = 0 for a..c-1, and rx = 1 for d..e-1, etc. Then select a y based on the rx set of ranges.
• Adithya: @ChrisHall that makes sense, is there a clean way to generalize that in a similar fashion to the calculation of N above or do I need to maintain a lookup table of some sort to keep track of what my constraints are with y with respect to x. I'll also post my own solution below of my some code in python that implements what you have above.
• Adithya: @ChrisHall I realize that my prior question is likely out of scope for the above question, so I summarized my newer attempts and put together a new question: stackoverflow.com/questions/60533510/…

Answer 2

Below is a Python implementation of the above algorithm from @Chris Hall's answer

def random_exclude(low: int, high: int, exclude: List[Tuple[int]]) -> int:
 N = -low+sum([(l-h) for l,h in exclude])+high
 r = np.random.randint(low, N)
 for l, h in exclude:
 if r < l:
 return r
 else:
 r+=h
 return r