以相同的概率從一組中選擇數字

從Steven Skiena的算法設計手冊中得到了這個問題。以相同的概率從一組中選擇數字

要求通過選擇K（值給出）編號，以從具有n個編號，給定的集合S形成一個子集S」，使得對於每個號碼選擇概率等於（K/N）。 n是未知的（我正在考慮將S作爲鏈接列表）。也，我們可以有僅通過集合S

2011-12-15 S..K

基本上相同http://stackoverflow.com/questions/5416567/random-selection/5417178＃5417178 – 2011-12-15 08:18:21

我認爲問題是不同的，因爲n是未知的。 – xdavidliu 2016-09-05 22:38:43

像這樣

for elem in S 
    if random() < (k - S'.size)/S.size // This is float division 
    S'.add(elem)

第一元件被選擇的概率k/n，第二個與(n-k)/n * k/(n-1) + k/n * (k-1)/(n-1)這減少了k/n等

來源

2011-12-15 07:57:43

當n是未知的你寧願需要在線算法所謂的水庫採樣。這裏提供http://propersubset.com/2010/04/choosing-random-elements.html

我的意思是這個算法用Python實現

好解釋&證明草圖

import random 
def random_subset(iterator, K): 
    result = [] 
    N = 0 

    for item in iterator: 
     N += 1 
     if len(result) < K: 
      result.append(item) 
     else: 
      s = int(random.random() * N) 
      if s < K: 
       result[ s ] = item 

    return result

來源

2012-05-04 13:34:51 Alec

你應該選擇一種算法，可以真正模擬真實的（從上面的鏈接所）活動。您的算法「隨機從n個數字中選擇k個」應該有兩個屬性

月底（1）它必須返回k個。

（2）必須真實地模擬該靶活性的性質：每個數字被選擇的概率是K/N。

Oboroks answer is wrong because it hasn噸第一屬性。

for i = 0 to n 
randomly choose an integer number between [1,n-i+1] 
if [randomValue <= (k - S'.size)/(S.size - i + 1)] then 
    S'.add(S[i])

隨着上述選擇方案中，每個號碼與概率K/n.You選擇可以看到，通過證明下面的等式：

https://www.facebook.com/photo.php?fbid=677984275648191&l=7cafe5d468

來源

2014-10-09 17:35:04

以相同的概率從一組中選擇數字

回答

相關問題