知識星球來自：Python那些事（微訊號：PythonSomething）
這幾天，網路上最火的就是錦鯉女孩，是國慶假期某支付平臺官微搞了個帶有錦鯉圖的轉發抽獎活動，一名網名叫@信小獃的獃萌小姐姐抽中了這個巨額大獎，小姐姐也因此又被廣大錦鯉愛好者們當成了“中國活體錦鯉”，瘋狂轉發。
自此之後，朋友圈，以及各大媒體論壇盛行各種“錦鯉”。作為程式員的我們，自然應該想一想，如何完成“錦鯉”的抽取？
實際這就是一個抽樣問題。可以抽象為如下問題：
-
隨機的選取容量為N的陣列中的k個元素，要求是不能重覆選取，並且不能刪除陣列中的元素，只能夠進行交換。其中 k≤N 。
看到這個問題，你想到了什麼？
我先想到的就是抽簽演演算法。當由 k 個人抽 K 張簽，無論先後順序，每個人抽中的機率都是1/K 。同理， k 個人抽 N 張簽，無論先後順序，每個人抽中的機率都是1/N 。
可以簡單說明一下：
1、當k=1時，由於是從 N 張簽中抽取，所以抽中的機率是1/N，成立。
2、當k=2時，在剩下的 N-1 個中隨機選：1/(N-1)，由於第1次沒有選中它， 而是在另外N-1個中選：(N-1)/N，因此機率為：(N-1)/N * 1/(N-1) = 1/N。
3、當k=3時，機率為 (N-1)/N * (N-2)/(N-1) * 1/(N-2) = 1/N。
4、重覆上述流程，到k=N。
既然如此，我們可以對N個數，進行k次抽簽操作，演演算法程式碼如下：
import random
def SelectRandomK(L, N, k):
for i in range(0, k):
# 產生i到N-1間的隨機數
j = random.randint(i, N - 1)
L[i], L[j] = L[j], L[i]這個演演算法實現的缺點就是依賴了資料總數N。如果不知道N有沒有辦法呢？
那就是蓄水池演演算法。蓄水池演演算法是大資料抽樣常用的演演算法，在不知道資料總數目的情況下可以完成隨機抽樣。
先從最簡單的蓄水池抽樣演演算法說起，即蓄水池中資料的數目為1。先把第一個資料以機率1/1放入蓄水池，第二個資料以1/2的機率替換蓄水池中資料，第三個資料以1/3的機率替換蓄水池中資料，第k個資料以1/k的機率替換蓄水池中資料，如此重覆，直至遍歷完所有的資料。
這樣完成後，每個資料被抽中的機率是相等的，即使不知道資料總數目。下麵，就用數學歸納法完成證明：
只需要證明當遍歷至第k行時，前面k行中的任意一行被抽取的機率均為1/k。
證明:（1）當i=1時，第一行被抽取的機率為1/1，成立。
（2）假設當i=k時成立，則前面k行中的任意一行被抽取的機率為1/k。現證明i=k+1時成立。
當i=k+1時，第k+1行替換原有樣本的機率為1/(k+1)，所以第k+1行被抽取的機率是1/(k+1)。
前面k行任意一行被抽取的機率為 1/k*k/(k+1)=1/(k+1)，
即當i=k+1時成立。證畢。
Python程式碼實現如下：
def SelectRandom1(L):
# 計數器
num = 2
for item in L[1:]:
if random.random() < 1.0/num:
L[0], L[num - 1] = L[num - 1], L[0]
num += 1那麼，如何以等機率選擇k個數呢？跟單個數類似，實現方法如下：
先把前k個資料放入蓄水池，對第k+1個資料，我們以 k/(k+1)機率決定是否要把它放入蓄水池，放入時隨機的選取一個作為替換項。對第n個資料，我們以 k/n機率決定是否要把它放入蓄水池，放入時隨機的選取一個作為替換項。這樣一直做下去，直至遍歷完所有的樣本空間。可以證明，對於任意的樣本空間N，對每個資料的選取機率都為k/N。
也可以透過數學歸納法完成證明：
只需要證明當遍歷至第n(n>=k)行時，前面n行中的任意一行被抽取的機率均為k/n。
證明:（1）當i=k時，前面k行被抽取的機率為k/k=1，成立。
（2）假設當i=n時成立，則前面n行中的任意一行被抽取的機率為k/n。現證明i=n+1時成立。
當i=n+1時，第n+1行替換原有樣本的機率為k/(n+1)，所以第n+1行被抽取的機率是k/(n+1)。
前面n行任意一行被抽取的機率為
k/n*(k/(n+1)*(k-1)/k+(n+1-k)/(n+1))=k/n*(n/(n+1))=k/(n+1)
即當i=n+1時成立。證畢。
Python程式碼實現如下：
def SelectRandomK(L, k):
# 計數器
num = k + 1
for item in L[k:]:
if random.random() < float(k/num):
# 產生0到k-1之間的隨機數
j = random.randint(0, k - 1)
L[num - 1], L[j] = L[j], L[num - 1]
num += 1關於隨機抽樣演演算法，你深入理解了嗎？ 你明白朋友圈“錦鯉”該如何抽取了嗎？
（完）
●編號528，輸入編號直達本文
●輸入m獲取文章目錄
演演算法與資料結構
更多推薦《18個技術類公眾微信》
涵蓋：程式人生、演演算法與資料結構、駭客技術與網路安全、大資料技術、前端開發、Java、Python、Web開發、安卓開發、iOS開發、C/C++、.NET、Linux、資料庫、運維等。