从 n 个数字中选出 m 个数字，保证这 m 个数字是以等概率的

问题如上。

这是我被http://www.wfuyu.com/cxyms/的1个题目。我的第1反应给出的解决办法是，开启  n 个线程并标记序号，各个线程打印出它的序号。直到有 m 个线程被调度时，停止所有线程。

打印出的序号即是 m 个等几率出现的数字。

http://www.wfuyu.com/cxyms/官听到这个解决办法，吸了1口冷气，估计心里在想，这小伙疯了！我当时自知这个解决方案不是http://www.wfuyu.com/cxyms/官想要的，因而说了，如果这个 n 很大，那末就要另

想办法了，由于不可能在1个进程里产生任意多个线程。

想啊想，过了两分钟，还是没有找到解决办法。http://www.wfuyu.com/cxyms/官很 nice 让我回去后再想想。

其实这个题细想，有些难度。你可能有1种思路：如果能1次性取出 m 个数字，再保证各数字是随机的，则可以满足等几率。但。。。如何1次性取出 m 个数字呢？

1次性生成多个随机数？如果生成的数字有相同则不是等几率的，由于这个数字比其它的数字出现的次数多，则几率大些（虽然你疏忽了它出现屡次）。或还有思路：

每次出1个，保证取 m 次得到的各数字几率相等。听起来，似乎这类思路要难些。

[解法1]

我们来摹拟这个进程，设有1个长度为 m 的辅助数组 B，用来装选中的数字。数组末满时，顺次从长度为 n 的数组 A 中每次取1个数字顺序放入 B 中。直到 B 满了。

设对后续的每个元素，其装入 B 中的几率为 x。此元素装入 B 中的操作是将它与 B 中的某个元素置换。

则 B 中已存在的某个元素，继续在 B 中存在的几率为：(1-x) + x*(m⑴)/m，即当前取出的元素不进入 B，被直接舍弃，或当前取出的元素进入 B ，但置换不产生在这个元素身上。

当前 A 中取出的元素，在 B 中存在的几率为 x。即，只要这个元素被选中，就1定会进入 B。

由于要使用每一个元素的几率相等，则有：

x = (1-x) + x*(m⑴)/m，故 x = m/(m+1)。

也即，按上面的操作便能保证每个被留下来的元素的几率相等且为 x ，即 m/(m+1)。

[解法2]

其实，我们斟酌1下，这个模型不就是抽奖的模型吗，有 n 张彩票，n 个人每人1张，如何选出 m 个人出来中奖。即，我们只需要摹拟1个公正的抽奖进程便能得到等几率的 m 个人。

我们都知道，抽奖不分前后，每一个人中奖的机率都1样。因此，最简单的做法是将 n 个人随机化排成1列，再取前 m 个人中奖便可。

那末，我们借助洗牌算法便能做到。那末，如何得到1个好的洗牌算法呢？1个可以证明是均匀的方法以下：

对第 i 张牌，它以 i/(i+1) 的几率与前面 i 张牌交换，实际操作时，可以生成1个 0 ~ i 之间的随机数，当其不为 i 时履行交换。交换的操作是：将此牌与前面 i 张牌随机交换。因而，可以证明，第 i 张牌在位置 i ，也即，它没有产生交换的几率为 1 - i/(i + 1)= 1/(i+1)。第 i 张牌在前面任何1个位置的几率为 i/(i+1)*1/i = 1/(i+1) 。但是，我们还需要证明，前 i 张牌中的任意1张在前面 i 个位置中的任意1个位置的几率为 1/(i+1) 才算是证明完全。如果直接入手，这个证明可以想象是相当复杂的。我们使用数学归纳法证明，按上面的操作，任意第 i 张牌被操作完成后，总共的 i + 1 张牌中的任意1张在0 ~ i 的任意1个位置上的几率为 1/(i + 1)。

证明：

当只有1张牌（第 0 张牌）时，在位置 0 上的几率为 1。

假定第 i 张牌被操作完成后，总共的 i + 1 张牌中的任意1张在0 ~ i 的任意1个位置上的几率为 1/(i + 1)。

则对第 i + 1 张牌被操作后：

前面已证明过，第 i+1 张牌放置在 0 ~ i+1 中的任意位置的几率为 1/(i+2)。对 0 ~ i 中的任意1张牌 x，它本来在 0 ~ i 上任意位置的几率为 1/(i + 1)。

x 被换到第 i+1 位置的几率为 (i+1)/(i+2) * 1/(i+1) = 1/(i+2)。x 现在还在 0 ~ i 位置的几率即 1 减去前者，为 : 1 - 1/(i+2)。而 0 ~ i 共有 i + 1 个位置，故 x 在任意1个位置的几率为：

(1 - 1/(i+2))*1/(i+1) 结果为 1/(i+2)。

因而就证明原结论。因此，这是1个平衡的洗牌算法。

[解法3]

如果我们每次在面临第 i 个元素，不是像解法1中的，保持1个固定的几率去决定该元素是不是留下，而是与当前已处理过的元素个数相干，能否得到1个解法呢？

设总共已处理的个数为 N，当前正要处理的是第 i 个元素。辅助数组为 B，源数组为 A。操作以下：

1.当 i <= m 时，元素留下。

2.当 i > m 时，使用几率 m/N 决定元素的去留。如果元素留下，则它随机与 B 中某个元素 x 置换（抛弃x，保存该元素）

证明等几率：

1.当 i = m + 1 时，此元素留下的几率为 m/(m+1)。B 中任意1个元素留下的几率为：1-m/(m+1) + m/(m+1)*(m⑴)/m = m/(m+1)。故此时，B 中所有元素的几率为 m/(m+1)。

2.设当已处理 N 个元素时，B 中的元素的几率为 m/N。

则当已处理 N+1 个元素时，当前元素留下的几率为 m/(N+1)。B 中任意1个元素留下的几率为：m/N*(1-m/(N+1) + m/(N+1)*(m⑴)/m) = m/(N+1)。最前面的 m/N 表示此元素在 B 中，否则不在 B 中。

故使用上面的操作方法，留下的元素的几率是相等的，且与总共处理的元素的个数是相干的。

这1模型和解法1中的模型是不相同的，注意区分：

解法1中的模型适用于保存下来的元素几率相等，且永久不变。

解法2中的模型适用于保存下来的元素几率相等，但随着处理的元素的个数增加而改变，这也意味着，当需要从未知数目的数据源中取 m 个数字，使其等几率，这类方法是非常适用的。

[解法4]

我们已有1个心得了，解法方案好像类似于：面临当前元素时，使用1个几率（这个几率多是动态变化的，或不变的）决定去留，若留，则与某个已选择的元素置换。下面再给出1种方法。

设 A 为源数组，B 为辅助数组（装入已选择的元素）。A 长度为 n，B 长度为 m，需要从 A 中取 m 个数字放入 B，使它们等几率。

遍历 A，在面临第 i 个元素 x 时，记 p 为还需要从 A 当选出的元素个数，q 为从 x 向后数，将 A 数完的个数，包括 x。决定 x 被选中的几率设置为 p/q。这也能够到达等几率。

1：第 0 个元素被选中的几率为 ：m/n

2：第 1 个元素被选中的几率为 ：m/n*(m⑴)/(n⑴) + (1-m/n)*m/(n⑴) = m/n

3：第 2 个元素被选中的几率为：... = m/n

....

依此类推，不管哪一个元素被选中的几率都为 m/n。下面，我们证明任意1个元素被选中的几率都为 m/n。

如果按上面的思路去证明将非常复杂，但是有1个很奇妙的证明方法。

我们看这个问题的模型，实际上，它就是1个抽奖模型，现在有1个箱子里面装着 n 张奖券，写着“中”，或“不中”，其中，写着“中”的有 m 张，现在问，第 k 次抽奖，中奖的几率为

多少？这明显为 m/n！还记得 "抽奖与顺序无关” 吗？因而，我们独立写出第 k 次中奖的几率的表达式：

C(m,1)*A(n⑴,m⑴) / A(n,m) = m/n。

故，上面的操作方法，任意1个元素被选中的几率都为 m/n。

解法4是对抽奖的全进程进行几率摹拟，而解法2是对抽奖的前置处理进行摹拟。

此解法的模型适用于保存下来的元素几率固定且相等。

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠