歡迎光臨
每天分享高質量文章

朋友圈“錦鯉”盛行,如何抽取“錦鯉”?

來自: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、資料庫、運維等。

赞(0)

分享創造快樂