基于概率选择随机项目

Question

这里有一个类似的问题，我知道，但是它让我感到困惑，所以我认为用我的方式更容易问出来。

所以我有一个由正数和负数值组成的数组。它们越高，被选择的可能性就越大。
我遇到了实际确定如何分配概率然后随机选择一个的问题。我猜数组需要先排序，但是在那之后我有点迷茫。

- FizzBuzz

---

如果您参考了之前的StackOverflow问题，无论是您自己还是别人提出的，即使是为了说明它没有帮助到您，请提供一个链接。StackOverflow上有无数的问题。 - Pascal Cuoq

已修复，对此表示抱歉。 - FizzBuzz

即使是针对C#，我发现http://www.vcskicks.com/random-element.php非常有帮助。 - N.N.

完整的C#代码，请参见...http://stackoverflow.com/a/33991225/294884 - Fattie

Answer 1

我有各种不同尺寸的咖啡杯。它们越大，我就要收取更高的费用。我在实际计算如何定价方面遇到了问题。

这不仅仅是一个编程问题 - 您已经指定概率随值增加而增加，但您没有说明如何随值增加。通常，咖啡店不会按照咖啡的数量直接收费。您不能按照价值比例分配概率，因为您的一些价值为负，但概率不能为负。

听起来您需要更明确地了解问题，然后才能编写任何代码。

如果您真的不关心概率与价值之间的关系，除了它们按值的顺序增加之外，那么一种简单的方法是：

• 对数组进行排序
• 将概率分配为第一个元素为1，第二个元素为2，依此类推。
• 现在，您分配的概率总和不为1，这是一个问题。因此，请将每个概率除以您分配的所有概率的总和：(1 + 2 +... + n) = n(n+1)/2。这称为“归一化”。

给定您的概率列表，总和为1，通常最简单的重复选择一个的方法是计算所有概率的累积概率，我将用示例进行演示：

value (sorted):           -12     -3      127    1000000
assigned probability:     0.1     0.2     0.3      0.4
cumulative probability:   0.1     0.3     0.6      1.0

累积概率定义为到该点的所有概率之和。

现在，从您的随机数生成器中，您需要一个介于0和1之间的随机（浮点）值。如果它位于0到0.1之间，则选择了-12。如果它位于0.1到0.3之间，则选择了-3，依此类推。要确定它属于哪个范围，您可以线性地遍历数组，或者可以执行二进制搜索。

如果愿意，您可以跳过归一化步骤和使用浮点数。分配“累积概率”（1、3、6、10 ...），但是要知道实际概率是存储的整数值除以n（n + 1）/ 2。然后从0到n（n + 1）/ 2-1中选择一个随机整数。如果它小于1，则选择第一个值，否则如果小于3，则选择第二个值，以此类推。这可能会使代码更清晰，但您的RNG在选择大范围的整数值方面可能做得好或不好。

请注意，您可以分配概率（0.001、0.002、0.003、0.994）而不是（0.1、0.2、0.3、0.4），仍然满足您的要求：“值越高，概率越高”。

- Steve Jessop

---

哦，对不起，数值越高，概率就越大。 一旦分配了概率，随机选择一个怎么样？ - FizzBuzz

啊哈，现在我明白了。比我能找到的任何其他解释都简单得多，非常感谢你。 - FizzBuzz

Answer 2

一种方法可以是

• 使所有值都为正数（将所有值的最小值的绝对值加到所有值上）
• 将值归一化为总和为1（将每个值除以值的总和）

现在要从生成的分布中随机化一个值，你可以：

• 在 [0,1] 上选择随机数。
• 开始累加概率，直到总和大于或等于随机值。选择该索引作为您的随机值。

- cjg

---

这种方法的问题在于最小值总是被赋予零概率。通常使用指数函数来强制保持正值。 - Lucas

Answer 3

在跟进Steve Jessop的建议后，当你从0到n（n + 1）/ 2-1选择一个随机整数后，你可以直接获取三角形根：(-1 + sqrt((8 * x) + 1)) / 2

- anon