生成不在一组数字 N 中的随机数 R 的最佳算法
我很想知道生成随机整数 R 的最佳方法是什么，该随机整数 R 不在提供的整数集中 (R∉N)。我可以想到几种方法来做到这一点，但我想知道你们都怎么想。
I am curious to know what the best way to generate a random integer R that is not in a provided set of integers (R∉N). I can think of several ways of doing this but I'm wondering what you all think.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
令 N 为整体集合的大小，令 K 为排除集合的大小。
I 取决于您从中采样的集合的大小。如果排除集远小于总体范围，则选择一个随机数，如果在排除集中，则重新选择。如果我们将排除集保留在哈希表中，则每次尝试都可以在 O(1) 时间内完成。
如果排除的集合很大，则在大小为 (N - K) 的集合中选择一个随机数 R，并将该选择输出为非排除元素的成员。如果我们仅将空洞存储在以随机数值作为键控的哈希表中，我们可以在一个样本中以 O(1) 的时间生成该值。
截止点将取决于 (N - K)/N 的大小，但我怀疑除非它大于 0.5 左右，或者您的集合非常小，否则在实践中仅进行采样直到命中会更快。
Let N be the size of the overall set, and let K be the size of the excluded set.
I depends on the size of the set you are sampling from. If the excluded set is much smaller than the overall range, just choose a random number, and if it is in the excluded set, choose again. If we keep the excluded set in a hash table each try can be done in O(1) time.
If the excluded set is large, choose a random number R in a set of size (N - K) and output the choice as the member of the non excluded elements. If we store just the holes in a hash table keyed with the value of the random number we can generate this in one sample in time O(1).
The cutoff point will depend on the size of (N - K)/N, but I suspect that unless this is greater than .5 or so, or you sets are very small, just sampling until you get a hit will be faster in practice.
鉴于您的描述有限？找到 N 中元素的最大值。仅生成大于该值的随机数。
Given your limited description? Find the maximum value of the elements in N. Generate only random numbers greater than that.
在整个域中生成您要使用的随机数 R（从最大值中减去 N 的大小）。然后循环遍历所有小于 R 的 N，并对每个 R 加 1。这将在域中给出一个不在 N 中的随机数。
Generate a random number R in the entire domain (subtract the size of N from the max value) that you want to use. Then loop through all N less than R and for each add 1 to R. This will give a random number in the domain that is not in N.