数组列表中的随机元素具有不同的机会

Question

正如在标题中所说，我想从一个使用不同“随机因子”的列表中随机取一个元素。背景如下：

• 我有一个类的列表，其中我不知道类的数量。
• 此列表中的所有类都使用返回列表中选定机会百分比的方法扩展公共超类。

我可能有一个想法，比如除了偶然的所有百分比类出现，如果超过100％，除各百分比，这样的相对机会仍然是相同的，但的总比例不超过100％。它可能不是很清楚，如果不是，我会多解释一下。

Answer 1

假设你在列表中3个对象，这些对象都有一个“百分比”（你真的应该叫“权重”，因为它不是一个百分比）的4,7和9

总和所有的权重：20

因此，第一个元件应平均地取出4超过了20倍，第二个有7 20等

所以，生成0和20。如果之间的整数结果在0到4之间，选择第一个元素。如果结果在4到11之间，选择第二个，如果结果在11到20之间，选择最后一个。

剩下的只是实现细节。

Answer 2

只是总结数字，创建一个随机值[0, 1)，mulitply的总和，并通过列表从结果中减去数字，直到你得到一个数< 0迭代：

List<MyClass> elements = ... 
double sum = elements.stream().mapToDouble(MyClass::getChance).sum(); 
double rand = Math.random() * sum; 
MyClass choice = null; 
for (MyClass e : elements) { 
    choice = e; 
    rand -= e.getChance(); 
    if (rand < 0) { 
     break; 
    } 
} 

Answer 3

如果”只要一次（或几次）完成查找，那么answer by @fabian是好的。

不过，若你打算做了很多，然后通过该解决方案进行顺序查找效率不高。

要获得更高效的解决方案，您需要更直接的查找，因此您需要按累积机会组织数据。这可以通过使用二分搜索的数组来完成，或者作为以累积机会为关键的一个数组。

随着NavigableMap如TreeMap，您就可以使用higherEntry(K key)找到所选对象：

返回用最少的键严格小于给定键大于或null如果关联的键 - 值映射有是不是这样的关键。

所以，这里是示例代码：

public class MyObj { 
    private final String name; 
    private final int weight; 
    public MyObj(String name, int weight) { 
     this.name = name; 
     this.weight = weight; 
    } 
    public String getName() { 
     return this.name; 
    } 
    public int getWeight() { 
     return this.weight; 
    } 
    @Override 
    public String toString() { 
     return this.name; 
    } 

    public static void main(String[] args) { 
     // Build list of objects 
     List<MyObj> list = Arrays.asList(
       new MyObj("A", 2), 
       new MyObj("B", 6), 
       new MyObj("C", 12) 
     ); 

     // Build map keyed by cumulative weight 
     NavigableMap<Integer, MyObj> weighedMap = new TreeMap<>(); 
     int totalWeight = 0; 
     for (MyObj obj : list) { 
      totalWeight += obj.getWeight(); 
      weighedMap.put(totalWeight, obj); 
     } 
     System.out.println(weighedMap); 

     // Pick 20 objects randomly according to weight 
     Random rnd = new Random(); 
     for (int i = 0; i < 20; i++) { 
      int pick = rnd.nextInt(totalWeight); 
      MyObj obj = weighedMap.higherEntry(pick).getValue(); 
      System.out.printf("%2d: %s%n", pick, obj); 
     } 
    } 
} 

样本输出

{2=A, 8=B, 20=C} 
14: C 
10: C 
9: C 
5: B 
11: C 
3: B 
1: A 
0: A 
1: A 
7: B 
4: B 
11: C 
17: C 
15: C 
4: B 
16: C 
9: C 
17: C 
19: C 
2: B