Выбор элемента с пропорциональной ему вероятностью в C#
 

Вопрос может быть уже задавался не раз, но тем не менее я нигде не нашел ответа на него.

Требуется выбрать число из массива с вероятностью, пропорциональной его величине. Это значит приблизительно следующее:
Есть массив, к примеру:
int var[] = new int[8];
var = {1, 0, 0, 2, 5, 2, 4, 1};

Нужен алгоритм, который бы возвращал одно из этих чисел, но с пропорциональной этому числу вероятностью, т.е. шансы быть выбранным у элемента '5' самые большие, а у элементов '0' - самые маленькие, но все же они должны выпадать.

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

первая мысль: делать много случайных чисел и записывать какое число сколько раз выпало.
Если выпал 0, записываем что он выпал один раз и генерируем снова. И так до того, пока у одного числа не наберётся максимальное количество выпаданий.

0 должен выпасть 6 раз
1 - 5 раза
2 - 4 раза
3 - 3 раза
4 - 2 раза
5 - 1 раз

Условия и взаимоисключающие.
Вероятность выпадения, пропорциональная нулю - нулю и равна.
Вычисляется так: единица (вероятность того, что выпадет хоть что-то) делится на сумму чисел и умножается на соответствующее число (необходимое условие пропорциональности). При этом ноль не выпадет никогда.
Следствия: если все элементы массива - нули, то задача решения не имеет. Ситуация "деление на ноль". Требуется встроить соответствующую проверку.
Дальше так: вызываем функцию находжения случайного числа в диапазоне от нуля до единицы и начинаем вычитать из него вероятности выпадения чисел в порядке их возрастания до того момента, пока не получим результат равный нулю или меньше нуля. Как только данный результат достигнут - выводим число, которому соответствует последняя вычтенная вероятность.
Пример: массив чисел {0, 1, 2 ,3 ,4 ,5}
соответствующие вероятности {0, 1/15, 2/15, 3/15, 4/15, 5/15}
пусть выпало случайное число=1/4
1/4-0=1/4, больше 0, продолжаем
1/4-1/15=11/60, больше 0, продолжаем
11/60-2/15=3/60, больше 0, продолжаем
3/60-3/15=-9/60, меньше 0, цикл завершён, выводим 3

Дальше снова берём случайное число и повторяем цикл.
Количество повторений цикла - столько, сколько нужно.

EvroStandart, Вашу мысль не понял. :idontnow:

В принципе - придумал, что сделать, чтобы ноль тоже выпадал (с исчезающе малой вероятностью).
Условие если результат равен нулю - выводить ноль, если меньше - число, которому соответствует последняя вычтенная вероятность.
Если на 10000 циклов хоть раз получим ноль - это уже довольно большая удача...

Я не думал о том, что у пятёрки вероятность равна 5%.

У меня просто выпадения с разной вероятностью. Чем больше цыфра, тем чаще будет выпадать.

добавлено через 4 минуты
Чтото сомнительно что при таком алгоритме 1 будет выпадать в пять раз реже чем 5.
надо проверять.

ЗЫ.
Проверил в экселе. Работает. Правда разбросы большие. Один раз из пятидесяти попыток 5 выпадает в шесть раз чаще, при другом запуске может быть только в два-три раза чаще.

не самый лучший метод проверки, мягко говоря...
Если случайное число действительно случайное с равномерным распределением на отрезке от 0 до 1. Т.е. с равной вероятностью выпадает любое число диапазона.
Алгоритм с вычитанием - фактически деление единичного отрезка на участки с длинами, соответствующими вероятностям выпадения чисел. Сортировка и вычитание - для упрощения алгоритма, не более того. Определяем, в какой из "участков вероятностей" попало наше случайное число.
Со слов воспринять довольно трудно, но можно попробовать нарисовать... ;) Отрезок из участков с длинами, соответствующими вероятностям, расположенными в порядке возрастания длин. Последовательно вычитая "длины участков" из случайного числа мы фактически определяем, в какой из "участков" оно попало.

P.S. Случай на картинке соответствует попаданию случайного числа точно в границу двух участков.

Зато быстро и сердито :biggrin:

Прикинул - вероятность такого события равна произведению погрешности вычислений с плавающей точкой на количество чисел в массиве.
Погрешность вычислений - определяется типом данных и используемой математической библиотекой. Для типа данных c# "decimal", к примеру, составляет порядка 10^-27 (если я ничего не путаю).
Хотя, повторюсь, если всё делать "по-честному", то при соблюдении пропорциональности ноль не выпадет никогда, ибо вероятность этого события равна (0*1/15) что согласно простейшей арифметике равно нулю. И хоть вы тресните - именно нулю, а не (6*10^-27), как получается при преднамеренном искажении логики программы...

Спасибо за предложенные варианты... Но, боюсь, такие алгоритмы будут тяжеловаты (в плане времени выполнения и вообще выполнимости) для моей программы.
Проблема заключается в том, что изначально массив забит нулями. А в процессе работы (при проводении сотен или даже тысяч итераций) его значения должны меняться. Я придумал возможный выход из такого положения, но хотелось бы услышать мнение экспертов, так сказать :)
Random ran = new Random();
int count = ran.Next(0, var.Sum());
int s = 0, giv = 0;
for(int i = 0; i < var.lenght; i++)
{
if(сount <= s) {giv = var[i]; break;}
s+= var[i];
}
Таким образом у нас будет сумма чисел, разбитая на кусочки, в один из которых должен угодить рандом. Как только мы видим, что рандомное число меньше начала следующего кусочка, берем число с индексом предыдущего и получаем как раз то, что нам требовалось выбрать.
Вроде бы, вероятности при этом не искажаются, но хочется быть уверенным.

"Вам шашечки или ехать?" :idontnow:
Мой алгоритм полностью соответствует постановке задачи (как я её понял из первого поста топика). Он возвращает случайный элемент массива с пропорциональной значению элемента вероятностью (для элементов с нулевым значением - с пренебрежимо малой фиксированной вероятностью, если брать модифицированный алгоритм).
Насчёт "тяжести" - да, есть такое дело. С ростом количества элементов массива чисел объём вычислений возрастает по экспоненте. "Прелести" вероятностных расчётов...
Для количества элементов массива в пределах 1000 - вполне быстро вычисляемо для более-менее современного компьютера. А если, скажем, ещё и CUDA задействовать, так и вообще до 100000 элементов без особых проблем...

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

Простите, но говоря об алгоритме - приводите пример алгоритма, а не кусок кода с туманными пояснениями... Да и задачу чётче формулируйте, ибо "правильно сформулированный вопрос содержит половину ответа"...

Понимаю, что вопрос прозвучит не в тему, но все же...
Random в C# видимо выдает случайное число, ориентируясь на время, поэтому он выдает несколько одинаковых чисел подряд. Это легко проверить, запустив рандом в цикле и записав результаты в массив.
Вот и хотелось бы знать, существует ли в C# получать все-таки разные числа, пусть и таким способом.

http://forum.codenet.ru/showthread.php?t=44530

Вкратце - инициализируйте генератор временем.

Именно потому, что я его инициализирую временем у меня и получается несколько одинаковых чисел подряд :) В одну миллисекунду успевает пройти 8-9 итераций и у всех одинаковые значения :). Но, насколько я понимаю, требуется, чтобы число, задающее рандом, изменялось с каждой итерацией, чтобы числа были разными?

Так инициализировать надо один раз, перед циклом (в конструкторе, или вообще перед запуском программы, если глобальный объект), а дальше уже в цикле получать случайные числа.