生成一个数字是范围(1,n)但不在列表中(i,j)

Question

如何生成范围内(1,n)但不在某个列表中的随机数(i,j)？

示例:range is (1,500),list is [1,3,4,45,199,212,344].

注意:列表可能未排序

Answer 1

拒绝抽样

一种方法是拒绝抽样:

1. 生成x范围内的数字(1,500)
2. 是x在你的禁止值列表？(可以使用哈希集进行此检查.)
   • 如果是,请返回步骤1
   • 如果不是,那么x你的随机值是否完成

如果您的允许值集合远远大于您的不允许值集合,这将正常工作:
如果有G可能的良好值和B可能的错误值,那么您需要x从G + B值中取样的预期次数,直到获得良好的价值是(G + B) / G(相关几何分布的期望).(你可以检查这一点.随着G无穷大,期望值达到1.随着B无穷大,期望变为无穷大.)

采样列表

另一种方法是列出L所有允许的值,然后进行采样L[rand(L.count)].