0

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:

Adithya
  • 63
  • 1
  • 8

2 Answers2

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...

Chris Hall
  • 1,707
  • 1
  • 4
  • 14
  • 2
    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)). – Dialecticus Mar 04 '20 at 13:42
  • 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. – Adithya Mar 04 '20 at 18:51
  • 1
    @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. – Chris Hall Mar 04 '20 at 19:04
  • @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 Mar 04 '20 at 19:13
  • @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: https://stackoverflow.com/questions/60533510/finding-unoccupied-bounding-boxes-in-an-image-given-a-set-of-occupied-boxes – Adithya Mar 04 '20 at 19:37
0

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
Adithya
  • 63
  • 1
  • 8