生成随机数但不循环排除多个范围

Question

我正在寻找一种在 [a, b) 之间生成随机数的数学方法，在 [c, d)、[e, f)、[g, h) 等处有空洞，其中 a < b 并且范围在范围内。

我在这里找到了很多关于如何在缺少一个范围的情况下使算法工作的示例，但似乎找不到一种 space/time 可以推广到多个范围的有效方法。我的意思是：

一个。所有可能范围的列表并从该列表中选择：不适用于大范围

b。生成一个随机数并检查它是否在范围之一，否则重试：unbounded terms of runtime

一些突出的测试用例可能是：

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

以下是我找到的一些示例：

Generating a random number between multiple ranges
Can Python generate a random number that excludes a set of numbers, without using recursion?

Answer 1

所以您想选择 a..c-1、d..e-1、...、x..b-1 中的任何一个？

所以N = (c-a) + (e-d) + ... + (b - x)。 Select 0..N-1 中的随机 r。如果 r < c，你就完成了。设置r = r + d，如果r < e，你就完成了...

Answer 2

下面是来自@Chris Hall 的回答

的上述算法的Python 实现

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

生成随机数但不循环排除多个范围

Generate random number but exclude multiple ranges without looping

algorithm

pseudocode