Выбор случайный элемент из списка с учетом вероятности каждого элемента

Question

К сожалению о плохо сформулированного названии ....

У меня есть объект с именем Ngram

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

Теперь предположим, что у меня есть список этих объектов, таких, что ...

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

Как выбрать случайный элемент из этого списка при факторизации распределения вероятностей.

Например, предположим, что grams[0].Probability == 0.5 то должно быть 50% вероятность выбора grams[0]

Я полагал, что, возможно, потребуется что-то вроде rand.NextDouble() но я в догадках.

Answer 1

Вот более универсальный способ чтобы сделать это (то есть вы не необходимости утверждать, что вероятности добавить к 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; 
} 

Answer 2

Сортировка списка, согласно Вероятность, по возрастанию.

Сумма поля вероятности для всех элементов в списке. Назовем эту сумму P.

Получить случайное число между [0, P], давайте назовем его г

Iterate списка, сохраняя при этом значения накопления суммы вероятностей до текущего элемента, который перебирает (pe). Завершение поиска, когда найти первый элемент, для которого ре> = г

Случай всех элементов массива подводить 1 теперь просто частный случай :)

Answer 3

в псевдокоде

r = Get a random number between 0 and 1 
sum = 0 
i = 0 
Loop 
    sum = sum + grams[i].Probability 
    If sum >= r Then 
     Exit Loop 
    End 
    i = i + 1 
End 
i is the index of the random item in the list 

Идея состоит в том, чтобы суммировать вероятность объекта до тех пор, пока сумма не станет больше или равна случайному числу. Поскольку сумма вероятностей до 1 и случайное число находятся в диапазоне 0 .. 1, вы найдете элемент в любом случае. Вероятнее всего, будут выбраны элементы с большей вероятностью.

∑P= 0 0.08  0.3 0.43 0.53   0.88 1 
    +--+--------+----+---+-------------+----+ 
    | |  | | |    | | 
    +--+--------+----+---+-------------+----+ 
i = 0  1  2 3  4   5 

Вы можете представить, что каждый элемент имеет длину, равную его назначенной вероятности. Алгоритм подобен случайному бросанию дротика на линейке длины один, причем все вероятности складываются вдоль линейки. Вероятность попадания элемента пропорциональна его размеру (то есть заданной вероятности).

Answer 4

Попробуйте это:

List<NGram> grams = new List<NGram>() 
{ 
    new NGram() { Probability = 0.5 }, 
    new NGram() { Probability = 0.35 }, 
    new NGram() { Probability = 0.15 } 
}; 

var rnd = new Random(); 

var result = 
    grams 
     .Aggregate(
      new { sum = 0.0, target = rnd.NextDouble(), gram = (NGram)null }, 
      (a, g) => 
       a.gram == null && a.sum + g.Probability >= a.target 
        ? new { sum = a.sum + g.Probability, a.target, gram = g } 
        : new { sum = a.sum + g.Probability, a.target, a.gram }); 

Это дает мне результаты, как это: