從列表中的隨機項目

Question

這更像是一個謎題。我想知道是否有一種方法可以從n個項目列表中選擇k個隨機項目，因爲n是未知的，我只想讀取一次項目列表。

謝謝

Answer 1

我猜的答案，我的問題是這樣的：

pick first k elements and store them into an array of length k 
for each element x > k 
    insert x with probability k/x 
    choose position at random between 1 and k 

Answer 2

簡單（如果k < = n）。這就像獲得k個號碼列表< n。這將是要獲得的數字位置的列表。創建範圍列表（0..n），從中獲得k個隨機數。直到最後一刻，您不必閱讀物品的實際列表。顯然，這只是有用的是最後的項目列表是慢讀（它是從磁盤或類似的東西讀取）。

爲了獲得項目的位置，只選擇做：

import random 
itemstopick = random.Random().sample(range(0,n), k) 

如果n，項目數是未知的，那麼你必須開始採摘第k個項目（即解決方案如果k = n）。然後，唯一的選擇是繼續閱讀物品，並選擇保留剛剛閱讀的新物品（並刪除另一個物品）或保持當前物品的狀態。要堅持一致的概率，您將不得不降低選擇最後一個讀取項目的概率。保持最後一項的概率應該總是P（k/n0），其中n0是當時n的值。我不相信你能做得比這更好。

如果你知道一些n的大小（值可以保證n大於它），只需要混合上面的兩個方法即可。首先用一個用minorant而不是n創建的列表，然後像未知n那樣繼續。

Answer 3

這取決於你是否有隨機值生成，如果你這樣做，比可能，如果不是你將不得不生成它們，你將需要從2 * k到3 * k左右的操作這種情況下，

Answer 4

1. 跳過隨機數從當前位置的項目列表
2. 就拿當前項目。
3. 如果您已到達列表的末尾，請跳到列表的開頭並轉到步驟1
4. 重複這些步驟k次。