# 隨機取出其中之一元素 ## 題目描述 一個文件中含有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。