3

来自编程珍珠：第 12 列：示例问题：

输入由两个整数m和n组成，其中m < n。输出是0..n-1范围内的m个随机整数的排序列表，其中没有任何整数出现超过一次。对于概率爱好者，我们需要一个无替换的排序选择，其中每个选择以相等的概率发生。

作者提供了一种解决方案：

initialize set S to empty
size = 0
while size < m do
    t = bigrand() % n
    if t is not in S
        insert t into S
        size++
print the elements of S in sorted order

在上面的伪代码中，bigrand()是一个函数返回一个大的随机整数（远大于m和n）。

谁能帮我证明上述算法的正确性？

根据我的理解，每个输出的概率应该是 1/C( n , m )。如何证明上述算法可以保证输出概率为 1/C( n , m )？

4

1 回答 1

1

该算法产生的每个解决方案都是有效的。

有多少解决方案？直到最后一行（排序）是n*(n-1)*(n-2)*..*(n-m)不同的排列或
n!/(n-m)!每个结果具有相同的概率

排序时，可能的解决方案数量会减少 m!。

所以可能的输出数量是n!/((n-m)!*m!)，这就是你所要求的。

n!/((n-m)!m!) = C(n,m)

于 2012-07-29T08:44:13.193 回答