算法题 - 随机取出其中之一元素

题目描述

一个文件中含有n个元素（n未知），要求在只能遍历一遍这n个元素的情况下，等概率随机的取出其中之一个元素。

分析与解法

假设5个人轮流抽签，只有其中某一个人能中签，那么，这5个人每个人中签的概率是相等的。不信的话，咱们可以具体计算下。

首先，第一个人中签的概率是1/5，第二个人中签的情况只能在第一个人未中时才有可能，所以第二个人中签的概率是4/5 X 1/4 = 1/5（4/5表示第一个人未中，1/4表示第二个人在剩下的4个签里中签的概率），所以，第二个人最终的中签概率也是1/5，

同理，第三个人中签的概率为：第一个人未中的概率 第二个人未中的概率 第三个人中的概率，即为：4/5 3/4 1/3 = 1/5，

一样的可以求出第四和第五个人的概率都为1/5，也就是说先后抽签顺序不影响每个人中签概率的大小。

回到咱们的问题，在明确了先后抽签顺序不影响不公平的原则之后，下面，给出选取策略：

顺序遍历，当前遍历的元素为第L个元素，变量e表示之前选取了的某一个元素，此时生成一个随机数r，如果r%L == 0(当然0也可以是0~L-1中的任何一个，概率都是一样的), 我们将e的值替换为当前值，否则扫描下一个元素直到文件结束。

你要是给面试官说明了这样一个策略后，面试官可能会问你这样做是等概率吗？那我们来证明一下。

在遍历到第1个元素的时候，即L为1，那么r%L必然为0，所以e为第一个元素，p=100%。遍历到第2个元素时，L为2，r%L==0的概率为1/2, 这个时候，第1个元素不被替换的概率为1*(1-1/2)=1/2,第1个元素被替换，也就是第2个元素被选中的概率为1/2,你可以看到，只有2时，这两个元素是等概率的机会被选中的。

同理，当遍历到第3个元素的时候，r%L==0的概率为1/3，前面被选中的元素不被替换的概率为1/2*(1-1/3)=1/3,前面被选中的元素被替换的概率，即第3个元素被选中的概率为1/3。

归纳法证明，这样走到第L个元素时，这L个元素中任一被选中的概率都是1/L，那么走到L+1时，第L+1个元素选中的概率为1/(L+1), 之前选中的元素不被替换，即继续被选中的概率为1/L*(1-1/(L+1)) = 1/(L+1)。证毕。

也就是说，走到文件最后，每一个元素最终被选出的概率为1/n， n为文件中元素的总数。

下面给出一个此选取策略的伪代码：

  Element RandomPick(file):
  Int length = 1;
  While (length <= file.size)
    If (rand() % length == 0)
      Picked = File[length];
    Length++;
  Return picked

举一反三

一个文件含有n个元素, n未知的情况下, 顺序遍历一遍, 要求等概率随机取r个，其中r < n。