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

Question

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

我在这里找到了许多示例，说明如果缺少一个范围，如何使算法起作用，但似乎找不到一种可以推广到多个范围的空间/时间有效方法。我的意思是：

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

湾。生成一个随机数并检查它是否是范围之一，否则重试：运行时的无限项

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

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

以下是我发现的一些示例：

• 在多个范围之间生成随机数

• Python 是否可以在不使用递归的情况下生成排除一组数字的随机数？

标签： algorithmpseudocode

Answer 1

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

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