How to pick an item by its probability?

Question

I have a list of items. Each of these items has its own probability.

Can anyone suggest an algorithm to pick an item based on its probability?

Answer 1

pretend that we have the following list

Item A 25%
Item B 15%
Item C 35%
Item D 5%
Item E 20%

Lets pretend that all the probabilities are integers, and assign each item a "range" that calculated as follows.

Start - Sum of probability of all items before
End - Start + own probability

The new numbers are as follows

Item A 0 to 25
Item B 26 to 40
Item C 41 to 75
Item D 76 to 80
Item E 81 to 100

Now pick a random number from 0 to 100. Lets say that you pick 32. 32 falls in Item B's range.

mj

Answer 2

Algorithm described in Ushman's, Brent's and @kaushaya's answers are implemented in Apache commons-math library.

Take a look at EnumeratedDistribution class (groovy code follows):

def probabilities = [
   new Pair<String, Double>("one", 25),
   new Pair<String, Double>("two", 30),
   new Pair<String, Double>("three", 45)]
def distribution = new EnumeratedDistribution<String>(probabilities)
println distribution.sample() // here you get one of your values

Note that sum of probabilities doesn't need to be equal to 1 or 100 - it will be normalized automatically.

Answer 3

1. Generate a uniformly distributed random number.
2. Iterate through your list until the cumulative probability of the visited elements is greater than the random number

Sample code:

double p = Math.random();
double cumulativeProbability = 0.0;
for (Item item : items) {
    cumulativeProbability += item.probability();
    if (p <= cumulativeProbability) {
        return item;
    }
}

Answer 4

If you don't mind adding a third party dependency in your code you can use the MockNeat.probabilities() method.

For example:

String s = mockNeat.probabilites(String.class)
                .add(0.1, "A") // 10% chance to pick A
                .add(0.2, "B") // 20% chance to pick B
                .add(0.5, "C") // 50% chance to pick C
                .add(0.2, "D") // 20% chance to pick D
                .val();

Disclaimer: I am the author of the library, so I might be biased when I am recommending it.