Java中的随机加权选择

Question

我想从一组中随机选择一个项目，但选择任何项目的机会应该与关联的权重成正比

示例输入：

 item                weight
----                ------
sword of misery         10
shield of happy          5
potion of dying          6
triple-edged sword       1

所以，如果我有 4 种可能的物品，那么得到任何一件没有重量的物品的几率是四分之一。

在这种情况下，用户获得苦难之剑的可能性应该是三刃剑的 10 倍。

如何在 Java 中进行加权随机选择？

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

Answer 1

我会使用 NavigableMap

 public class RandomCollection<E> {
    private final NavigableMap<Double, E> map = new TreeMap<Double, E>();
    private final Random random;
    private double total = 0;

    public RandomCollection() {
        this(new Random());
    }

    public RandomCollection(Random random) {
        this.random = random;
    }

    public RandomCollection<E> add(double weight, E result) {
        if (weight <= 0) return this;
        total += weight;
        map.put(total, result);
        return this;
    }

    public E next() {
        double value = random.nextDouble() * total;
        return map.higherEntry(value).getValue();
    }
}

假设我有一份动物狗、猫、马的清单，概率分别为 40%、35%、25%

 RandomCollection<String> rc = new RandomCollection<>()
                              .add(40, "dog").add(35, "cat").add(25, "horse");

for (int i = 0; i < 10; i++) {
    System.out.println(rc.next());
}

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