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

#php #массивы #случайные_числа

Есть такой набор данных:

$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

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


Ответ 2

Попробуйте хранить интервалы вероятностей для каждого элемента:

Элемент №1 - от 0 (включительно) до 1 (не вкл.)
Элемент №2 - от 1 (вкл.) до 6 (не вкл.)
Элемент №3 - от 6 (вкл.) до 16 (не вкл.)

Теперь ваша задача заключается в том, чтобы взять случайное число от 0 до 15, проверить,
в какой интервал оно попадает и взять соответствующий элемент.


Ответ 3

Решил похожую задачу просто -  указал диапазон чисел для слов. 
Чем больше диапазон чисел для слова, тем больше вероятность его вывода.

$bb = rand(0,1000);

if ($bb >= 0 && $bb <= 700) {
   echo "значение 1 ".$bb;
}

elseif ($bb >= 701 && $bb <= 1000) {
   echo "значение 2 ".$bb;
}