隨機拉動P A組

的不同元件我需要一個函數pull(S,p)採用一個有序集S和若干p與p < n = |S|，使得其返回的Sp隨機選擇的和不同的元素的列表。隨機拉動P A組

假設s_i,i = 1, ..., n是S的i'th元素。那麼問題就是隨機產生{1, ..., n}範圍內的不同索引，並用這些索引來提取元素。

我該如何做到這一點？在此範圍內生成p隨機數字是不夠的，因爲這可能會導致衝突，修復衝突似乎效率低下。

2014-03-05 Undreren

@hivert是的，這個問題已經被問了很多次。儘管如此，鏈接的副本沒有弗洛伊德的抽樣算法作爲答案，這太糟糕了。 –

取出集合的元素後，將該集合的最後一個元素與此元素交換。然後你減少設置的大小1.然後你重複獲取元素隨機（）*大小的集合。

2014-03-05 10:02:09 Lampard

這需要我對前一組中的項目進行重新排序，這可能會產生負面影響。這可以通過創建一組新的'n'元素來避免，但是這個算法是'O（n）'。我們可以將函數減少到「O（p）」嗎？ – Undreren

你可以保留一個你如何修改集合的日誌。日誌只是您每次都拿出的元素的索引數組。得到結果後，您可以輕鬆地通過此日誌恢復集。時間和空間都是O（p） – Lampard

一種方法是洗牌指數{1, ..., n}並採取第一p元素的索引

2014-03-05 10:22:57 Nishanth

你打算如何洗牌？ – Undreren

[Fisher Yates Shuffle]（http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle） – Nishanth

回答