從 n 個數字中選出 m 個數字，保證這 m 個數字是以等概率的

問題如上。

這是我被http://www.vxbq.cn/cxyms/的1個題目。我的第1反應給出的解決辦法是，開啟  n 個線程并標記序號，各個線程打印出它的序號。直到有 m 個線程被調度時，停止所有線程。

打印出的序號即是 m 個等幾率出現的數字。

http://www.vxbq.cn/cxyms/官聽到這個解決辦法，吸了1口冷氣，估計心里在想，這小伙瘋了！我當時自知這個解決方案不是http://www.vxbq.cn/cxyms/官想要的，因而說了，如果這個 n 很大，那末就要另

想辦法了，由于不可能在1個進程里產生任意多個線程。

想啊想，過了兩分鐘，還是沒有找到解決辦法。http://www.vxbq.cn/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是對抽獎的前置處理進行摹擬。

此解法的模型適用于保存下來的元素幾率固定且相等。

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈