随机取出其中之一元素

题目描述

一个文件中含有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为文件中元素的总数。

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

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

举一反三

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