给定每个项目的概率，从列表中选择随机项目 [英] Selecting Random Item from List given probability of each item

问题描述

抱歉标题用词不当....

Sorry about badly phrased title....

我有一个名为 NGram 的对象

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.

例如，假设 grams[0].Probability == 0.5 那么应该有 50% 的机会选择 grams[0]

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

我想我可能需要像 rand.NextDouble() 这样的东西，但我不知所措.

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

推荐答案

这里有一个更通用的方法(意味着你不需要需要断言概率加到 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;
}

这篇关于给定每个项目的概率，从列表中选择随机项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！