Zufälliges Element aus Array-Liste mit verschiedenen Chancen

Question

Wie im Titel erwähnt, möchte ich ein zufälliges Element aus einer Liste mit anderen "Randomization-Faktor" nehmen. Der Kontext ist wie folgt:

• Ich habe eine Liste von Klassen, in denen ich die Anzahl der Klassen nicht kenne.
• Alle Klassen in dieser Liste erweitern eine gemeinsame Oberklasse mit einer Methode, die einen prozentualen Anteil der Wahrscheinlichkeit zurückgibt, dass sie in der Liste ausgewählt werden.

ich eine Idee, für die Prozentsätze der Möglichkeit, alle wie zusätzlich können die Klassen erscheinen, und wenn es 100% übersteigt, die jeweils den Prozentsatz unterteilen, so dass die relativen Chancen immer noch die gleichen sind, aber die der Gesamtprozentsatz überschreitet nicht 100%. Es ist vielleicht nicht sehr klar, wenn es nicht ist, werde ich ein bisschen mehr erklären.

Answer 1

Angenommen, Sie 3 Objekte in der Liste, und diese Objekte haben einen „Prozentsatz“ (die Sie wirklich „Gewicht“ sollten nennen, da es nicht ein Prozentsatz ist) alle 4, 7 und 9.

Sum die Gewichte: 20.

So sollte das erste Element 4 im Durchschnitt von 20-mal sein, die zweite 7 von 20 usw.

So ausgesucht, eine ganze Zahl zwischen 0 und 20. Wenn erzeugen Das Ergebnis liegt zwischen 0 und 4. Wählen Sie das erste Element aus. Wenn das Ergebnis zwischen 4 und 11 liegt, wählen Sie das zweite und wenn das Ergebnis zwischen 11 und 20 liegt, wählen Sie das letzte aus.

Der Rest ist nur Implementierungsdetails.

Answer 2

einfach die Zahlen zusammenzufassen, erstellen Sie einen zufälligen Wert in [0, 1), mulitply durch die Summe und iteriert durch die Liste, die Zahlen aus dem Ergebnis subtrahiert, bis Sie eine Nummer < 0 erhalten:

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

Wenn Sie‘ Ich werde die Suche nur einmal (oder ein paar Mal) machen, dann ist die answer by @fabian gut.

Wenn Sie jedoch viel unternehmen, ist die von dieser Lösung durchgeführte sequenzielle Suche nicht effizient.

Für eine effizientere Lösung benötigen Sie eine gezieltere Suche, so dass Sie die Daten nach der kumulativen Chance organisieren müssen. Dies kann als ein Array unter Verwendung der binären Suche oder als NavigableMap erfolgen, die durch die kumulative Wahrscheinlichkeit codiert ist.

Mit einem NavigableMap wie TreeMap, können Sie dann higherEntry(K key) verwenden das ausgewählte Objekt zu finden:

Gibt einen Schlüssel-Wert-Zuordnung mit dem geringsten Schlüssel zugeordnet ist strikt größer ist als der vorgegebene Schlüssel oder null wenn es ist kein solcher Schlüssel.

Also hier ist, Beispielcode:

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); 
     } 
    } 
} 

Beispielausgabe

{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