这是一道作业题。为了打印 [0,N) 范围内 M 个排序的不同随机整数,我们可以使用以下算法:
int n = N
int m = M
for i in [0,N)
if (bigrandom() % n--) < m)
print i
m--
正如我们所知,该算法以相等的概率选择范围内的所有整数。你能帮我证明一下吗?
最佳答案
- 选中任何特定数字的几率是
m/n
。 - 如果选择这个数字,我们会遇到同样的问题,但是
n' = n - 1
和m' = m - 1
。如果不是,我们有同样的问题,但n' = n - 1
和m' = m
。
您的算法是这个想法的实现。
您还需要证明假设 1
,但您可能可以自己做。
关于algorithm - 如何证明采样算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4293622/