生成一个范围为(1，n)但不在列表(i，j)中的数字 [英] Generate a number is range (1,n) but not in a list (i,j)

问题描述

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

How can I generate a random number that is in the range (1,n) but not in a certain list (i,j)?

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

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

注意:列表可能未排序

推荐答案

拒绝抽样

一种方法是拒绝采样:

Rejection Sampling

One method is rejection sampling:

1. 生成范围为(1，500)的数字x
2. x是否在您的不允许值列表中? (可以将哈希集用于此检查.)
   • 如果是，请返回步骤1
   • 如果否，则x是您的随机值，完成

1. Generate a number x in the range (1, 500)
2. Is x in your list of disallowed values? (Can use a hash-set for this check.)
   • If yes, return to step 1
   • If no, x is your random value, done

如果您的允许值集明显大于您的不允许值集，这将很好地工作:
如果存在G个可能的好值和B个可能的坏值，则您的预期次数必须从G + B值中采样x，直到获得一个好的值是(G + B) / G(相关几何分布的期望值). (您可以检查一下.G达到无穷大时，期望值变为1.B达到无穷大时，期望值变为无穷.)

This will work fine if your set of allowed values is significantly larger than your set of disallowed values:
if there are G possible good values and B possible bad values, then the expected number of times you'll have to sample x from the G + B values until you get a good value is (G + B) / G (the expectation of the associated geometric distribution). (You can sense check this. As G goes to infinity, the expectation goes to 1. As B goes to infinity, the expectation goes to infinity.)

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

Another method is to make a list L of all of your allowed values, then sample L[rand(L.count)].

这篇关于生成一个范围为(1，n)但不在列表(i，j)中的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！