从百分比列表中获取一个随机对象

Question

我似乎找不到一个有效的方法来选择一个随机对象以每个对象的百分比选择。

基本上，我给该方法一个对象映射，并有可能选择该对象的机会。最好是我想要它，这样它可以有很多小数，因为最长的小数也可以。

也很好。

public static <T> T random(Map<T, Double> chances) {
    T toReturn = null;
    double rand = new Random().nextInt(1000) / 10.0D;
    // ???
    return toReturn;
}

预先感谢。

Answer 1

基本策略：

1. 计算从0％（包括100％）的随机百分比rand
2. 迭代地图的入口表
3. 对于每个条目，如果值小于rand，则返回键
4. 否则，向兰特添加价值并继续

Answer 2

此问题称为"适应性相称的选择"，您无法在Wikipedia上找到更多信息（和示例代码）。

Answer 3

如果每个对象都映射到概率（大概添加到100），那么您别无选择，只能通过它们迭代：

public static <T> T getRandomItem(Map<T, Double> chances) {
    double chance = random.nextDouble() * 100.0;
    double cumulative = 0.0;
    for (T item: chances.keySet()) {
        cumulative += chances.get(item);
        if (chance < cumulative)
            return item;
    }
    throw new IllegalStateException("chances don't sum to 100");
}

Answer 4

我做了帕特里克·帕克（Patrick Parker）告诉我要做的事情，这是完美的！非常感谢。

public static <T> T random(CustomMap<T, Double> map) {
    double rand = (double) new Random().nextInt(10000001) / 100000.0D;
    double total = 0.0D;
    for (T t : map.getKeys()) {
        double chance = map.get(t);
        total += chance;
        if (total >= rand) return t;
    }
    return null;
}

Answer 5

在这种情况下，我将使用具有累积机会的列表。假设您有五个对象，机会为0.1、0.3、0.2、0.1、0.3。然后，我将创建一个新的数组a，其中值a = [0.1、0.4、0.6、0.7、1.0]，也就P_0 p_n是对象n的可能性。然后，您可以创建一个随机数r并在a中找到最高元素x，以使a [x]> r，x是所需对象的索引。

伪：

cumulative_chances = [chances[0]]
for i=1 to chances.size()
    cumulative_chances.append(chances[i]+cumulative_chances[i-1])
r=random(0, cumulative_chances.last())
i=0
while cumulative_chances[i]<r
   i++
return i

请注意，我假设所有n的p_n> 0。如果您想将任何项目的概率设置为完全为零，则必须稍微修改。

如果您的应用程序中的任何内容都对性能敏感，则可以在功能中进行此计算。在其他情况下，我会预测它。请注意，伪代码对值的归一化不敏感。他们不需要将UPP添加到1（或100个如果您需要百分比），无论如何它都可以。