如何從一個集合中隨機選取一個隨機的所有物品？

Question

我收集了一些對象的集合，我一次只檢查一個對象，直到檢查完所有對象。每個對象都由預定義的權重選擇，並有許多可能的重複項。最終結果將是集合中項目的有序列表。什麼是有效的方式來獲得這個清單？

考慮，例如，與指定的卷的以下球：

A: 2 
B: 3 
C: 25 
D: 100 

讓我們添加4個所述的球，3個乙球，1C球，和2個d球的袋子。假設繪製一個特定的球的概率與其體積成正比，那麼在這一點上繪製一個特定的D球的概率是100/242（它們具有相同的權重但不相同）。假設這個D被繪製並繼續。此時抽出C球的機率是25/142，因爲之前D球被移除。假設你在這裏畫出C球並繼續。繼續繪製，直到所有球被移除，以便您擁有像DCDBABBA這樣的序列。

Answer 1

[編輯：更新後添加單個球號碼]

假設有k不同類型的n球。創建一個表示初始狀態的(balltype, weight, count)三元組的k - 元素數組。當你做到這一點，每增加weight[i] * count[i]到total，其中在0

首先開始了，成立了球數的數組，每個球類型：

1. 對於i 1至k：
   • 創建count[i] - 元素陣列b[i]，1 < = j的< = count[i]分配j到b[i][j]。

現在隨機挑一個球。下面的步驟可以重複n次挑所有的球在一些隨機順序：

1. 選擇介於0和total的隨機整數r - 1，包括端值。
2. 設置p = 0
3. 對於i 1至k：
   • 添加weight[i] * count[i]到p。
   • 如果r < p：
     • 我們挑選了一個類型爲balltype[i]的球。輸出它。
     • 選擇1和count[i]之間的隨機整數c，包括1和count[i]。
     • 輸出b[i][c]作爲球號碼。
     • 減1減1 count[i]。
     • 設置b[i][c] = b[i][count[i]]。這使未使用的球數「密集」。
     • Set total = total - weight[i]。
     • 停止。

挑出所有n球將採取O（nk）時間。只要count[i]達到0（即當i類型的所有球已經用完）並且將n減1時，通過將三元組陣列中的最後一個條目移動到位置i，可以將該速度加快大約2倍，但是對於代碼選擇球號碼繼續工作，要麼整個陣列b[n]也必須複製到b[i]，或者必須使用另一個間接層。