數組列表中的隨機元素具有不同的機會

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