LINUX.ORG.RU
Форум — Development  

«Любимчики» и случайный выбор.


0

0

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

простой случай: А(ранк 1), В (ранк2), С(ранк4) -
можно создать временный массив АВВСССС и бросать жребий из него, но...
проблемма усложняется: А(0.2345) В(3.498) С(0.2344) - тут
вышеуказанный метод не покатит. А вот что да покатит - не могу додуматься
Спасибо

★★
← C#(mono)
g95 vs Intel Fortran 8 →

А random разве не real возвертает?

А ежли и нет -- ну, округли, скажем, до тысячных и выбирай из своего массива в тыщу элементов...

С уважением -- Смоляное Чучелко

anonymous
()

ну, э... тут много вариантов есть, я что то похожее делал для перовода ф-ии распределения в набор частиц и обратно... но время позднее, башка не варит:-)

В общем ИМНО алгоритм след:

1) нормировка (просуммировать все ранки. пусть сумма S)

2) такая хитрая шняга как типа аналог. участка числ. прямой [0:S] он побит на отрезки, соотв ранкам. Генератор случ чисел выдает число от 0 до S, дальше индексация по шняге и получаешь элемент массива.

Вопрос в том как шнягу реализовать. Сходу проситься метод половинного деления (то есть каждый элемент массива имеет поле Srank = сумме ранков предшественников. Ну и по этим полям с-но и ищешь пока случ. сило не попадет в вилку [Srank, rank])

AIv ★★★★★
()

тупой способ:
за один проход по всем элементам вычисляем сумму рангов S
берем случайное число X равномерно распределенное на [0,S]
второй раз проходим по всем элементам, вычисляя частичные суммы.
возвращаем тот элемент на котором частичная сумма превысит X

хитрый способ:
зачем, если первый способ работает?

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← C#(mono)
Development
g95 vs Intel Fortran 8 →