如何按概率选择一个项目？

Question

我有一个项目清单。这些项目中的每一个都有自己的概率。

任何人都可以建议一种算法来根据概率选择一个项目吗？

原文由 Ruzanna 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

因此，每个项目存储一个标记其相对概率的数字，例如，如果您有 3 个项目，其中一个被选中的可能性应该是其他两个中的任何一个的两倍，那么您的列表将具有：

  [{A,1},{B,1},{C,2}]

然后对列表的数字求和（在我们的例子中为 4）。现在生成一个随机数并选择该索引。 int index = rand.nextInt(4);返回数字，使索引在正确的范围内。

Java代码：

 class Item {
    int relativeProb;
    String name;

    //Getters Setters and Constructor
}

...

class RandomSelector {
    List<Item> items = new List();
    Random rand = new Random();
    int totalSum = 0;

    RandomSelector() {
        for(Item item : items) {
            totalSum = totalSum + item.relativeProb;
        }
    }

    public Item getRandom() {

        int index = rand.nextInt(totalSum);
        int sum = 0;
        int i=0;
        while(sum < index ) {
             sum = sum + items.get(i++).relativeProb;
        }
        return items.get(Math.max(0,i-1));
    }
}

原文由 Usman Ismail 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

1. 生成均匀分布的随机数。
2. 遍历你的列表，直到被访问元素的累积概率大于随机数

示例代码：

 double p = Math.random();
double cumulativeProbability = 0.0;
for (Item item : items) {
    cumulativeProbability += item.probability();
    if (p <= cumulativeProbability) {
        return item;
    }
}

原文由 Brent Worden 发布，翻译遵循 CC BY-SA 3.0 许可协议