假设5个人轮流抽签,只有其中某一个人能中签,那么,这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时,这两个元素是等概率的机会被选中的。

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

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