How to pick an item by its probability?

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

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

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 beforeEnd - Start + own probability

The new numbers are as follows

Item A 0 to 25Item B 26 to 40Item C 41 to 75Item D 76 to 80Item 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