Random weighted selection in Java

Question

I want to choose a random item from a set, but the chance of choosing any item should be proportional to the associated weight

Example inputs:

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

So, if I have 4 possible items, the chance of getting any one item without weights would be 1 in 4.

In this case, a user should be 10 times more likely to get the sword of misery than the triple-edged sword.

How do I make a weighted random selection in Java?

Answer 1

I would use a 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();     } } 

Say I have a list of animals dog, cat, horse with probabilities as 40%, 35%, 25% respectively

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

There is now a class for this in Apache Commons: EnumeratedDistribution

Item selectedItem = new EnumeratedDistribution<>(itemWeights).sample(); 

where itemWeights is a List<Pair<Item, Double>>, like (assuming Item interface in Arne's answer):

final List<Pair<Item, Double>> itemWeights = Collections.newArrayList(); for (Item i: itemSet) {     itemWeights.add(new Pair(i, i.getWeight())); } 

or in Java 8:

itemSet.stream().map(i -> new Pair(i, i.getWeight())).collect(toList()); 

Note: Pair here needs to be org.apache.commons.math3.util.Pair, not org.apache.commons.lang3.tuple.Pair.