Выбор случайного элемента массива, вероятность выпадания которого предопределена

Есть такой набор данных:
$items = array( array( 'name' => 'Элемент #1', 'chance' => 1, ),
array( 'name' => 'Элемент #2', 'chance' => 5, ),
array( 'name' => 'Элемент #3', 'chance' => 10, ), );
Для каждого элемента массива предопределена вероятность — в ключе 'chance'
Задача: выбрать случайный элемент из этого набора, учитывая, что вероятность того что выпадет «Элемент #2» в 5 раз выше, чем «Элемент #1», а «Элемент #3» — в 10 раз выше, чем у «Элемент #1».
Если точнее, то, наверно, так:
Элемент #1 — вероятность: 1/16 Элемент #2 — вероятность: 5/16 Элемент #3 — вероятность: 10/16
Набросал такой алгоритм
$items = [...]; // входной массив (см. выше)
$items_set = array();
foreach ($items as $item_id => $item) { for ($i = 0; $i < $item['chance']; $i++) $items_set[] = $item_id; }
// теперь $items_set представляет собой такой массив: // [0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] // то бишь, индекс элемента входного массива повторяется столько, // сколько у него «шансов» быть избранным
$rand_id = $items_set[array_rand($items_set)]; $rand_item = $items[$rand_id];
На выходе $rand_item хранит как-раз то, что необходимо — один из элементов входного массива. И все бы хорошо, если бы при добавлении элемента с вероятностью 200, массив $items_set не рос на 200 элементов. И таких может быть несколько.
Вопрос: есть ли какой-то более адекватный способ решения задачи? Если алгоритм будет уметь оперировать с элементами с вероятностью = 0.5 — будет вообще здорово (мой вариант к этому не приспособлен, приходится предварительно подбирать множитель для всех «шансов» так, чтобы минимальный был = 1).

Ответ

да, такой алгоритм есть. Он заключается в том, что нужно сформировать массив вида [1,6,16]. ( То есть, если есть массив вероятностей [1,5,10], то нужный массив это такой, что элемент в позиции n - это сумма элементов первого массива от 1 до n). Последний элемент этого массива - это суммарное кол-во вариантов. Как использвоать: генерируем случайное число и проходим по массиву, пока не найдем элемент, который больше сгенерированного числа (я предполагаю, что случайные числа генерятся в диапазоне от 0 до сумма минус 1). Но если элементов больше 7-10, то лучше уже подумать о бинарном поиске, благое дело, он будет быстрым (массив то гарантированно отсортирован).