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

问题描述

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

我在这里找到了许多示例，说明了在缺少一个范围的情况下如何使该算法起作用，但似乎找不到能推广到多个范围的时空有效方法.我的意思是这两者:

a.所有可能范围的列表，并从该列表中进行选择:不适用于大范围

b.生成随机数并检查它是否是范围之一，否则请重试:运行时的无限制条件

一些重要的测试案例可能是:

  generate_random(start = 0，end = 100，排除:[[2,50)，(51，100)])generate_random(开始= 0，结束= 1e16，排除:[[1e6,1e7)，(1e3，1e4)]) 

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

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

解决方案

所以您要选择 a..c-1 ， d..e-1 中的任何一个code>，...， x..b-1 吗?

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

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?

解决方案

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

这篇关于生成随机数，但排除多个范围而不循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！