algorithm - “编程珍珠”:从序列中采样m个元素

从编程珍珠：Column 12: A Sample Problem：
输入由两个整数m和n组成，m范围为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）？

最佳答案

该算法得到的每个解都是有效的。
有多少种解决方案？
到最后一行（排序）是不同的排列或
n*(n-1)*(n-2)*..*(n-m)并且每个结果都有相同的概率
当你排序时，你将可能的解决方案的数量减少了m！是的。
所以可能的输出数是n!/(n-m)!，这是您所要求的。
n!/((n-m)!*m!)

关于algorithm - “编程珍珠”:从序列中采样m个元素，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11706920/