algorithm - "Programming Pearls": Sampling m elements from a sequence

Question

来自 Programming Pearl:Column 12: A Sample Problem :

The input consists of two integers m and n, with m < n. The output is a sorted list of m random integers in the range 0..n-1 in which no integer occurs more than once. For probability buffs, we desire a sorted selection without replacement in which each selection occurs with equal probability.

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

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)概率的输出？

Answer 1

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

有多少种解法？到最后一行(排序)是 n*(n-1)*(n-2)*..*(n-m) 不同的排列或
n!/(n-m)! 并且每个结果都有相同的概率

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

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

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