How to pick an item by its probability?

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?

Solution 1:

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

Solution 2:

So with each item store a number that marks its relative probability, for example if you have 3 items one should be twice as likely to be selected as either of the other two then your list will have:

 [{A,1},{B,1},{C,2}]

Then sum the numbers of the list (i.e. 4 in our case). Now generate a random number and choose that index. int index = rand.nextInt(4); return the number such that the index is in the correct range.

Java code:

class Item {
    int relativeProb;
    String name;

    //Getters Setters and Constructor
}

...

class RandomSelector {
    List<Item> items = new List();
    Random rand = new Random();
    int totalSum = 0;

    RandomSelector() {
        for(Item item : items) {
            totalSum = totalSum + item.relativeProb;
        }
    }

    public Item getRandom() {

        int index = rand.nextInt(totalSum);
        int sum = 0;
        int i=0;
        while(sum < index ) {
             sum = sum + items.get(i++).relativeProb;
        }
        return items.get(Math.max(0,i-1));
    }
}

Solution 3:

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