從加權概率列表中隨機選擇

Question

我有一個N個元素的數組（表示給定字母表的N個字母），並且該數組的每個單元格都包含一個整數值，該整數值表示一個字符串中出現的次數給出了那封信的文本。現在我想隨機選擇從所有的字母一個字母在字母表的基礎上，他與給定約束的出現次數：

• 如果這封信具有正（非零）值，那麼就可以總是由算法選擇（當然，有更大或更小的概率）。

• 如果字母A的值比字母B的值高，那麼它必須更有可能被算法選擇。現在

，考慮到這一點，我想出了一個簡單的算法，可以做的工作，但我只是想知道是否有更好的事情要做。這似乎相當重要，我認爲爲了更有效地完成這項工作，可能會有更多聰明的事情要做。這是我認爲的算法：

• 將數組中的所有頻率相加。將其存儲在SUM中
• 選擇從0到SUM的隨機值。將其存儲在RAN中
• [While] RAN> 0，從第一個開始，訪問陣列中的每個單元（按順序），並從RAN中減去該單元格的值
• 最後訪問的單元格是選定的單元格

那麼，還有比這更好的事情嗎？我錯過了什麼嗎？

我知道大多數現代計算機可以計算這麼快，我甚至不會注意到，如果我的算法效率低下，所以這是一個更理想的問題，而不是一個實際的問題。

我更喜歡解釋的算法，而不僅僅是代碼的答案，但如果你更自在地在代碼中提供你的答案，我沒有問題。

Answer 1

的想法：

• 迭代通過所有的元素和設置的每個元素作爲累計頻率的值迄今。
• 生成一個介於1和所有頻率之和的隨機數字
• 對這個數字的值做一個binary search（找到第一個大於或等於數字的值）。

實施例：

Element A B C D 
Frequency 1 4 3 2 
Cumulative 1 5 8 10 

生成在1-10範圍內的隨機數（1 + 4 + 3 + 2 = 10時，相同的累積列表的最後一個值），做二進制搜索，這將如下返回值：

Number Element returned 
1  A 
2  B 
3  B 
4  B 
5  B 
6  C 
7  C 
8  C 
9  D 
10  D 

Answer 2

的Alias Method已攤銷O（1）每生成的值的時間，但需要每個查找2和制服。基本上，您創建一個表，其中每列包含要生成的值之一，第二個值稱爲別名，以及在值和別名之間進行選擇的條件概率。使用你的第一套制服以相同的可能性挑選任何一列。然後根據你的第二套制服在主要價值和別名之間選擇。它需要O（n log n）的工作來爲n個值初始建立一個有效的表，但是在表的內置生成值是恆定時間之後。您可以下載this Ruby gem以查看實際的實施。 Marsaglia等人的另外兩種非常快速的方法。被描述爲here。他們提供了C implementations。