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

Question

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

示例:范围是 (1,500)，列表是 [1,3,4,45,199,212,344]。

注意:列表可能未排序

Answer 1

Rejection Sampling

一种方法是拒绝抽样:

1. 生成一个范围为 (1, 500) 的数字 x
2. x 是否在您的不允许值列表中？ (可以使用散列集进行此检查。)
   • 如果是，返回步骤1
   • 如果不是，x 是你的随机值，完成

如果允许的值集明显大于不允许的值集，这将正常工作:
如果有 G 可能的好值和 B可能的错误值，那么在获得良好值之前，您必须从 G + B 值中采样 x 的预期次数是 (G + B)/G(相关几何分布的期望值)。 (你可以感觉到检查这一点。随着 G 趋于无穷大，期望趋于 1。随着 B 趋于无穷大，期望趋于无穷大。)

对列表进行抽样

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