Случайные элементы C#
Простая проблема: у меня есть список элементов, и я хочу выбрать один случайным образом на основе вероятности каждого элемента.
Природа «случайности» здесь не важна, более важна вероятность того, что каждый элемент (например, в массиве) выбран по сравнению с другими элементами.
Пример
Итак, предположим, что у нас есть четыре элемента, и у каждого из них имеется 25% вероятность быть выбранным:
|
1 2 3 4 |
A - 25% B - 25% C - 25% D - 25% |
Как мы можем случайным образом выбираем один? В .NET это легко, используем класс Random мы можем генерировать псевдослучайное число между 0 и 3 (индексом), и это будет элемент, который мы случайным образом выбрали. Это работает, потому что вероятность выбора одного из четырех элементов одинакова для всех них.
Но теперь давайте изменим список:
|
1 2 3 4 |
A - 35% B - 15% C - 40% D - 10% |
Мы больше не можем просто случайно выбрать индекс.
Статистика
Ответ довольно прост с некоторыми базовыми знаниями статистики. Вместо того, чтобы случайным образом выбирать индекс, мы генерируем случайное число от 0 до 100 (или 0,0 и 1,0) и сравниваем его с кумулятивной вероятностью каждого элемента. Кумулятивная вероятность — это просто вероятность элемента плюс вероятность всех элементов перед ним.
Давайте применим это к нашему примеру, сначала отсортируем элементы:
|
1 2 3 4 5 |
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#
Это сайт кодирования, поэтому давайте запишем несколько простых строк кода:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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 в зависимости от вашего диапазона). Простой факт, но может вызвать некоторые проблемы, если забыть.