Random element from array list with different chances

Question

As said in title, I would like to take a random element from a list using different "randomization factor". The context is as follows:

• I have a list of classes, in which I don't know the number of classes.
• All of the classes in this list extend a common superclass with a method returning a percentage of chance for them to be chosen in the list.

I may have an idea, like addition all the percentages of chance for the classes to appear and if it exceeds 100 %, divide each of the percentage so that the relative chances are still the same, but the total percentage does not exceed 100 %. It may not be very clear, if it isn't i'll explain a bit more.

Answer 1

Suppose you have 3 objects in the list, and these objects have a "percentage" (that you should really call "weight", since it's not a percentage) of 4, 7 and 9.

Sum all the weights: 20.

So the first element should be picked out 4 out of 20 times on average, the second one 7 out of 20, etc.

So, generate an integer between 0 and 20. If the result is between 0 and 4, pick the first element. If the result is between 4 and 11, pick the second one, and if the result is between 11 and 20, pick the last one.

The rest is just implementation details.

Answer 2

Just sum up the numbers, create a random value in [0, 1), mulitply by the sum and iterate through the list subtracting the numbers from the result until you get a number < 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

If you're just going to do the lookup once (or a few times), then the answer by @fabian is good.

If you however are going to do it a lot, then the sequential search performed by that solution is not efficient.

For a more efficient solution, you need a more directed lookup, so you need to organize the data by the cumulative chance. This can be done as an array using binary search, or as a NavigableMap keyed by the cumulative chance.

With a NavigableMap such as TreeMap, you can then use higherEntry(K key) to find the selected object:

Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key.

So, here is sample code:

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

Sample Output

{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