Sélection pondérée aléatoire en Java

Question

Je veux choisir un article au hasard dans un ensemble, mais la chance de choisir n'importe quel article doit être proportionnelle au poids associé

Exemples d'entrées :

 item                weight
----                ------
sword of misery         10
shield of happy          5
potion of dying          6
triple-edged sword       1

Donc, si j'ai 4 articles possibles, la chance d'obtenir un article sans poids serait de 1 sur 4.

Dans ce cas, un utilisateur devrait avoir 10 fois plus de chances d'obtenir l'épée de la misère que l'épée à trois tranchants.

Comment faire une sélection aléatoire pondérée en Java ?

Answer 1

J'utiliserais un NavigableMap

 public class RandomCollection<E> {
    private final NavigableMap<Double, E> map = new TreeMap<Double, E>();
    private final Random random;
    private double total = 0;

    public RandomCollection() {
        this(new Random());
    }

    public RandomCollection(Random random) {
        this.random = random;
    }

    public RandomCollection<E> add(double weight, E result) {
        if (weight <= 0) return this;
        total += weight;
        map.put(total, result);
        return this;
    }

    public E next() {
        double value = random.nextDouble() * total;
        return map.higherEntry(value).getValue();
    }
}

Disons que j'ai une liste d'animaux chien, chat, cheval avec des probabilités de 40%, 35%, 25% respectivement

 RandomCollection<String> rc = new RandomCollection<>()
                              .add(40, "dog").add(35, "cat").add(25, "horse");

for (int i = 0; i < 10; i++) {
    System.out.println(rc.next());
} 

Answer 2

Vous ne trouverez pas de framework pour ce genre de problème, car la fonctionnalité demandée n'est rien de plus qu'une simple fonction. Faites quelque chose comme ceci :

 interface Item {
    double getWeight();
}

class RandomItemChooser {
    public Item chooseOnWeight(List<Item> items) {
        double completeWeight = 0.0;
        for (Item item : items)
            completeWeight += item.getWeight();
        double r = Math.random() * completeWeight;
        double countWeight = 0.0;
        for (Item item : items) {
            countWeight += item.getWeight();
            if (countWeight >= r)
                return item;
        }
        throw new RuntimeException("Should never be shown.");
    }
}

Answer 3

139

Il existe un algorithme simple pour choisir un élément au hasard, où les éléments ont des poids individuels :

1. calculer la somme de tous les poids

2. choisissez un nombre aléatoire égal ou supérieur à 0 et inférieur à la somme des poids

3. parcourir les éléments un à la fois, en soustrayant leur poids de votre nombre aléatoire jusqu'à ce que vous obteniez l'élément où le nombre aléatoire est inférieur au poids de cet élément