Привет! 
Прошу помочь придумать алгоритм для такой задачи: 

Есть набор объектов (A, B, C, D), у каждого своя вероятность, что сейчас выпадит именно он, например для A - 50%, B - 20%, C - 30%, D - 0%(не выпадит никогда).  Какой-то объект должен быть обязательно выбран, но какой именно - зависит от вероятности каждого. Т.е. понятно, что A будет чаще других, D - никогда.
Этот момент критичен по времени выполнения, надо чтобы быстро. 

Не могу никак придумать првильный алгоритм. 

Люди подсказывают так:



Или для N объектов:



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

Но главное - все же не очень правильно вычисляется вероятность, как мне кажется.

Есть идеи, что можно ещё придумать?

использовать приоритетную очередь? ;)

А как обеспечить, чтобы объект, у которого вероятность больше, чаще стоял на выходе?

что значит "чаще" ?
у кого приоритет выше - тот первым выйдет.
для того чтоб очередь использовать многократно - при выходе элемента, добавляем его обратно.

или я не правильно понял задачу?

Добавлено через 3 минуты и 2 секунды
и да - с приоритетными очередями есть проблема: нет стандартной реализации "хорошей" приоритетной очереди. та, что в стандартной библиотеке - ужасная реализация.элементы с более низкими приоритетами вовсе никогда не выйдут, пока имеются элементы с более высокими приоритетами.

хорошая реализация есть в boost: http://www.boost.org/doc/libs/1_49_0/doc/html/heap.html

Добавлено через 6 минут и 36 секунд
приоритеты элементов можно изменять. значит, распределение можно регулировать.

Понял верно. 
Спасибо за наводку на приоритетную очередь, буду пробовать. Единственное условие - буст не вариант использовать в текущем проекте, нельзя его с собой таскать, придётся разбираться и писать самому

Если будут ещё идеи, прошу высказываться 

Это сообщение отредактировал(а) Riddik - 24.2.2012, 15:23

что значит "таскать" ?
для готового продукта, исходники буста таскать не нужно 

Не так выразился 
Нельзя его использовать - подключать к текущему проекту. Такие условия.

Как вариант можно взять массив из 100 элементов и заполнить его согласно твоим процентам: у А будет 50 позиций, у Б - 30 и тд.
брать рендомное число в пределах 0-99 и смотреть на какую позицию попадешь.
в итоге будет нормальное распределние.

хотя это не очень красиво, да.

ан нет. это уже предлагали. сорри.

Это сообщение отредактировал(а) Michrutka - 24.2.2012, 17:03

Всё равно спасибо!

Это сообщение отредактировал(а) Riddik - 24.2.2012, 17:35

Вот, набросал.

http://liveworkspace.org/code/daa70b237fe8...296788da0592921

Большое спасибо!