java - 从每个元素具有特定概率的数组中随机选择一个元素

Question

我希望从数组中随机选择元素，其中每个元素都有特定的被选择概率。有没有一种有效的方法来做到这一点，或者可能已经内置在 Java 中的东西可以做到这一点？

Answer 1

一种方法是使用这样的加权概率：

MyClass getRandomElement(MyClass[] elements)
{
    int totalWeight = 0;
    for (MyClass element : elements)
    {
       totalWeight += element.weight;
    }

    int position = new Random().nextInt(totalWeight);

    for (MyClass element : elements)
    {
       if (position < element.weight)
       {
           return element;
       }
       position -= element.weight;
    }
    throw new IllegalStateException("Should never get here");
}

Answer 2

一种 O(log(n)) 方法（这是直接从一个非常相似的问题的答案中提取的）：

通常的技术是将数组转换为累积和数组：

 [10 60 5 25]  --> [10 70 75 100]

在从零到累计总数的范围内选择一个随机数（在示例中：0 <= x < 100）。然后，在累积数组上使用二分法将索引定位到原始数组中：

Random variable x      Index in the Cumulative Array      Value in Original Array
-----------------      -----------------------------      ----------------------
 0 <= x < 10                      0                            10
10 <= x < 70                      1                            60
70 <= x < 75                      2                             5
75 <= x < 100                     3                            25 

例如，如果随机变量x为 4，则将累积数组二等分给出位置索引 0，对应于原始数组中的 10。

并且，如果随机变量x为 72，则将累积数组二等分给出位置索引 2，对应于原始数组中的 5。

Answer 3

一种方法是构建一个数组，其中包含根据需要重复的项目以表示它们的概率。因此，如果数组中的项目 A 的概率为 0.3，项目 B 的概率为 0.7，您可以将它们放入一个包含 10 个项目的数组中，其中 A 重复 3 次，B 重复 7 次。

然后您可以使用随机数生成器从数组中选择一个索引。

另一种解决方案是将每个项目及其概率加载到数据结构中，将每个概率表示为一个范围（即项目 A 可以表示范围 .5-.8），然后从 0-1 生成一个随机值并获取随机数落入的任何范围的值。

Answer 4

如果您对选择数组中的元素的概率权重进行编码（可能通过数组中对象的成员变量），您可以执行以下操作：

1. 假设您有权重为整数的元素。
2. 将所有元素的权重相加。
3. 创建一个介于 1 和该权重之间的随机值。
4. 遍历数组，计数直到匹配随机值。

例子：

[1, 3, 2, 5, 2] 总和 = 13 随机掷骰 = 5

element[0] ..（我们数到了1）

element[1] ..（我们数到了 4）

element[2] .. (我们已经数到 6) 6 > 5 因此我们选择 2。

现在，这需要 O(n) 时间，其中 n 是数组中值的数量。为了提高效率，更好的方法是将值放置在值指示的位置。这有点像：

[a，b，b，b，c，c，d，d，d，d，d，e，e]。

查找计数排序以获取更多详细信息；它允许 O(1) 访问。

Answer 5

我个人喜欢使用 NavigableMap 的方法。这种方法看起来像这样

interface Weighted {
    public double getWeight();
}

class UnbalancedRandomizer <E extends Weighted> {
    private NavigableMap<Double, E> container = new TreeMap<>();

    UnbalancedRandomizer(E... elements) {
        for (E element : elements) {
            add(element);
        }
    }

    public void add(E element) {
        double offset = container.isEmpty() ? 0.0 : container.lastEntry().getKey();
        container.put(offset + element.getWeight(), element);
    }

    public E getRandom() {
        double rolled = container.lastEntry().getKey() * Math.random();
        return container.ceilingEntry(rolled).getValue();
    }
}

但是，当您想要删除元素或更改元素的权重时，这可能会变得有点棘手。毕竟我相信在大多数用例中，只有 add 才是真正相关的。这些主要是发生事件的查找表（例如老虎机符号机会）或用于对重量/大小/年龄等属性进行分组的匹配器。

示例用法

class Foo implements Weighted {
    private double weight;
    private String name;

    public Foo(double weight, String name) {
        this.weight = weight;
        this.name = name;
    }

    @Override
    public double getWeight() {
        return weight;
    }

    @Override
    public String toString() {
        return "Symbol{" +
                "weight=" + weight +
                ", name='" + name + '\'' +
                '}';
    }

    public static void main(String... args) {
        UnbalancedRandomizer<Foo> randomizer = new UnbalancedRandomizer(
                new Foo(10, "A"),
                new Foo(30, "B"),
                new Foo(50, "C"),
                new Foo(50, "D")
        );

        Stream.generate(randomizer::getRandom).limit(50).forEach(System.out::println);
    }
}

示例输出

Symbol{weight=50.0, name='C'}
Symbol{weight=50.0, name='C'}
Symbol{weight=50.0, name='D'}
Symbol{weight=50.0, name='C'}
Symbol{weight=30.0, name='B'}
Symbol{weight=50.0, name='C'}
Symbol{weight=50.0, name='C'}
Symbol{weight=50.0, name='C'}
Symbol{weight=50.0, name='D'}
Symbol{weight=50.0, name='D'}
Symbol{weight=50.0, name='D'}
Symbol{weight=50.0, name='D'}
Symbol{weight=50.0, name='C'}
Symbol{weight=50.0, name='C'}
Symbol{weight=50.0, name='D'}
Symbol{weight=50.0, name='C'}
Symbol{weight=50.0, name='C'}
Symbol{weight=50.0, name='D'}
Symbol{weight=50.0, name='C'}
Symbol{weight=50.0, name='C'}
Symbol{weight=50.0, name='C'}
Symbol{weight=50.0, name='C'}
Symbol{weight=30.0, name='B'}
Symbol{weight=50.0, name='C'}
Symbol{weight=50.0, name='C'}
Symbol{weight=50.0, name='C'}
Symbol{weight=30.0, name='B'}
Symbol{weight=50.0, name='D'}
Symbol{weight=30.0, name='B'}
Symbol{weight=50.0, name='C'}
Symbol{weight=50.0, name='C'}
Symbol{weight=30.0, name='B'}
Symbol{weight=50.0, name='C'}
Symbol{weight=10.0, name='A'}
Symbol{weight=30.0, name='B'}
Symbol{weight=30.0, name='B'}
Symbol{weight=50.0, name='D'}
Symbol{weight=50.0, name='C'}
Symbol{weight=30.0, name='B'}
Symbol{weight=10.0, name='A'}
Symbol{weight=50.0, name='C'}
Symbol{weight=50.0, name='C'}
Symbol{weight=50.0, name='D'}
Symbol{weight=50.0, name='D'}
Symbol{weight=30.0, name='B'}
Symbol{weight=50.0, name='D'}
Symbol{weight=50.0, name='C'}
Symbol{weight=50.0, name='D'}
Symbol{weight=10.0, name='A'}
Symbol{weight=50.0, name='D'}