Выбор случайных элементов на основе вероятности

Случайные элементы C#

Простая проблема: у меня есть список элементов, и я хочу выбрать один случайным образом на основе вероятности каждого элемента.

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

Пример

Итак, предположим, что у нас есть четыре элемента, и у каждого из них имеется 25% вероятность быть выбранным:

A - 25%
B - 25%
C - 25%
D - 25% 

Как мы можем случайным образом выбираем один? В .NET это легко, используем класс Random мы можем генерировать псевдослучайное число между 0 и 3 (индексом), и это будет элемент, который мы случайным образом выбрали. Это работает, потому что вероятность выбора одного из четырех элементов одинакова для всех них.

Но теперь давайте изменим список:

A - 35%
B - 15%
C - 40%
D - 10%

Мы больше не можем просто случайно выбрать индекс.

Статистика

Ответ довольно прост с некоторыми базовыми знаниями статистики. Вместо того, чтобы случайным образом выбирать индекс, мы генерируем случайное число от 0 до 100 (или 0,0 и 1,0) и сравниваем его с кумулятивной вероятностью каждого элемента. Кумулятивная вероятность — это просто вероятность элемента плюс вероятность всех элементов перед ним.

Давайте применим это к нашему примеру, сначала отсортируем элементы:

Element - Probability - Cumulative Probability
   D          10%               10%
   B          15%               25%
   A          35%               60%
   C          40%               100%

Теперь давайте представим что мы кинули кубик… допустим, мы получим 53. Мы сравниваем это число с кумулятивной вероятностью каждого элемента и выбираем первую, которая находится в пределах диапазона. Таким образом, D составляет 10%, а не в пределах 53. Далее идет B, 25%, ничего хорошего. Далее идет А, 60%, то есть больше 53! Таким образом, элемент, случайно выбранный с нашим случайным числом 53, равен A.

Это имеет смысл, потому что элементам с низкой вероятностью потребуется небольшое случайное число, чтобы их можно было выбрать сразу. Элементы с более высокой вероятностью будут «использовать» вероятность того, что меньшие из них будут иметь больше шансов быть выбранными.

Код C#

Это сайт кодирования, поэтому давайте запишем несколько простых строк кода:

List<KeyValuePair<string, double>> elements = ...some data
Random r = new Random();
double diceRoll = r.NextDouble();

double cumulative = 0.0;
for (int i = 0; i < elements.Count; i++)
{
    cumulative += elements[i].Value;
    if (diceRoll < cumulative)
    {
        string selectedElement = elements[i].Key;
        break;
    }
}

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

И последнее замечание. Это довольно очевидно, но убедитесь, что вероятность всех элементов складывается до 1 (или 100 в зависимости от вашего диапазона). Простой факт, но может вызвать некоторые проблемы, если забыть.