Selecting Random Item from List given probability of each item

Question

Sorry about badly phrased title....

I have an object called NGram

class NGram
{
     //other properties
     double Probability {get; set;} //Value between 1 and 0 
}

Now suppose I have a list of these objects such that...

List<NGrams> grams = GetNGrams();
Debug.Assert(grams.Sum(x => x.Probability) == 1);

How can I select a random item from this list while factoring in the probability distribution.

For instance, suppose grams[0].Probability == 0.5 then there should be a 50% chance of selecting grams[0]

I figured I may need something like rand.NextDouble() but I am at loss.

Answer 1

Here's a more generic way to do it (meaning you don't need to assert that the probabilities add to 1):

static Random rand = new Random();

public NGram GetRandom(IEnumerable<NGram> pool)
{
     // get universal probability 
     double u = pool.Sum (p => p.Probability);

     // pick a random number between 0 and u
     double r = rand.NextDouble() * u;

     double sum = 0;
     foreach(NGram n in pool)
     {
         // loop until the random number is less than our cumulative probability
         if(r <= (sum = sum + n.Probability))
         {
            return n;
         }
     }
     // should never get here
     return null;
}