c - 根据概率选择随机项目

Question

有一个 similar question ，我知道，但这让我很困惑，所以我认为用我的方式提问更容易。

所以我有一组值，正值和负值。他们越高，他们被选中的可能性就越大。
我实际上很难弄清楚如何分配概率，然后随机选择一个。我猜想首先需要对数组进行排序，但在那之后我有点迷路了。

Answer 1

“我有各种不同尺寸的咖啡。它们越大，我就越想为它们收取更多费用。我实际上很难弄清楚如何分配价格”。

这不仅仅是一个编程问题 - 您已经指定概率随着值的增加而增加，但是您没有说如何它随着值的增加而增加。通常，咖啡店的收费与咖啡量不成正比。您不能分配与值成比例的概率，因为您的某些值是负数，但概率不能为负数。

听起来您需要在编写任何代码之前进一步确定问题。

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

• 对你的数组进行排序
• 为第一个元素分配概率 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，依此类推。要找出它位于哪个范围，您可以线性遍历数组，也可以进行二分查找。

如果需要，您可以跳过规范化步骤和 float 的使用。分配“累积概率”(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)，并且仍然满足“值越高，概率越高”的要求。