从加权概率名单中随机选择 [英] Randomly choosing from a list with weighted probabilities

问题描述

我有N个元素（重presenting一个给定的字母表中的N个字母）组成的数组，数组中的每个单元包含一个整数值，该整数值意味着在一个给定的文本出现的次数信。现在我想随机选择从所有在字母表的字母一个字母的基础上，他的出现给定的约束条件的数量：

I have an array of N elements (representing the N letters of a given alphabet), and each cell of the array holds an integer value, that integer value meaning the number of occurrences in a given text of that letter. Now I want to randomly choose a letter from all of the letters in the alphabet, based on his number of appearances with the given constraints:

• 如果信具有正（非零）的值，则它可以总是由算法选择（具有更大或更小的概率，当然）

• If the letter has a positive (nonzero) value, then it can be always chosen by the algorithm (with a bigger or smaller probability, of course).

如果一个字母A具有更高的价值比字母B，则它必须是更可能通过算法来选择

If a letter A has a higher value than a letter B, then it has to be more likely to be chosen by the algorithm.

现在，考虑到​​这一点，我想出了一个简单的算法，可以做的工作，但我只是想知道是否有更好的事情。这似乎是很基本的，我觉得可能是更聪明的事情要做，以更有效地做到这一点。这是算法我想：

Now, taking that into account, I've come up with a simple algorithm that might do the job, but I was just wondering if there was a better thing to do. This seems to be quite fundamental, and I think there might be more clever things to do in order to accomplish this more efficiently. This is the algorithm i thought:

• 添加了阵列中的所有频率。它存储在SUM
• 选择一个随机值从0到总和。它存储在RAN
• [虽然] RAN> 0，从第一个开始，参观每个单元阵列中（按顺序），并从RAN减去单元格的值
• 最后所处的小区是被选中的人

那么，有没有更好的事情做的比呢？我失去了一些东西？

So, is there a better thing to do than this? Am I missing something?

我知道最现代的计算机可以计算出该这么快我甚至不会注意到，如果我的算法是无效的，所以这更是一个理论问题，而不是一个实际的问题。

I'm aware most modern computers can compute this so fast I won't even notice if my algorithm is inefficient, so this is more of a theoretical question rather than a practical one.

我preFER的解释算法，而不是仅仅code的答案，但如果你更舒适的提供在code你的答案，我对此没有问题。

I prefer an explained algorithm rather than just code for an answer, but If you're more comfortable providing your answer in code, I have no problem with that.

推荐答案

的想法：

• 在遍历所有元素，并设置每个元素的累积频率的数值迄今。
• 生成和1之间的随机数的所有频率之和
• 请在值a 二进制搜索以这个号码（找到第一个值大于或等于所述数目）

• Iterate through all the elements and set the value of each element as the cumulative frequency thus far.
• Generate a random number between 1 and the sum of all frequencies
• Do a binary search on the values for this number (finding the first value greater than or equal to the number).

示例：

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

生成的范围内的随机数的1-10（1 + 4 + 3 + 2 = 10，同样如在累积列表的最后一个值）中，执行二进制搜索，这将如下返回值：

Generate a random number in the range 1-10 (1+4+3+2 = 10, the same as the last value in the cumulative list), do a binary search, which will return values as follows:

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

这篇关于从加权概率名单中随机选择的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！