从M个数中随机取出N个

看到这样一个题目：在M个数中，随机取出其中的N个，要求等概率。

这应该是一个比较简单的题目，看到题目后的第一想法是：维护一个关于这M个数的集合，然后每次随机从集合中抽一个数，抽N次即可。
等概率显然不是什么问题，当然前提是假设随机函数是等概率的，否则任何方法都免谈了。
对于其中的每一个数，它在每一次不被抽走的概率是：(M-1)/M、(M-2)/(M-1)、...、(M-N)/(M-N-1)，到最后还没被抽走的概率就是(M-N)/M，也就是说它会被抽走的概率是N/M。

看到一个网友的解决思路，感觉很有意思：

在M个数中，随机取出其中的N个，那么每个数被选中的概率都是N/M。

对于其中的第一个数字，它被选中的概率是N/M，所以随机生成一个来自(0,1)之间的均匀分布的实数u。
如果u<N/M，则这个数被选中。于是问题简化为：对于剩下的M-1个数，等概率选择其中的N-1个，每个数被选中的概率都是(N-1)/(M-1)；
否则，这个数字不被选中。问题简化为：对于剩下的M-1个数，等概率选择其中的N个，每个数被选中的概率都是N/(M-1)；

简单分析一下概率：对于这第一个数字，它被选中的概率就是N/M。
对于剩下的M-1个数，任何一个数被选中的概率是： N/M * (N-1)/(M-1) + (1-N/M) * N/(M-1) = N/M. 因此满足题意。

这样的思路让人很受启发……