Как сделать рандом из массива с указанной вероятностью для элементов?

Question

[l4m3r]

Есть массив вида:

$a = [
     'a' => 1,
     'b' => 0.11,
     'c' => 0.5,
     'd' => 1,
     'e' => 0.02,
     'f' => 0.0000005,
// ...
];

Значения в массиве != вероятность (0 - 1), а лишь вес / частота.
Мне нужно сделать такой рандом, который чаще всего будет возращать тот ключ, у которого больший вес.
Т.е. согласно примеру выше, чаше всего будет выпадать 'a' или 'd', крайне редко 'e'

PS: была подобная тема, но там немного не то.

Answer 1

[Сергей Соколов]

Сложить все веса. Их сумма это 100%, «единица».
Взять случайное число от 0 до 1.
Спроецировать на ваш диапазон, посмотреть, куда попали.

$sum = array_sum($a);
$rnd = rand() / getrandmax(); // от 0 до 1
$runningSum = 0;
foreach($a as $k => $v) {
  $runningSum += $v / $sum;
  if ($runningSum >= $rnd) {
    $key = $k;
    break;
  }
}
if (!$key) $key = $k;

echo "Выпало: " . $key . PHP_EOL;

Comments

[l4m3r]

Нет! Их сумма не равна 1! Это просто числа! Чем больше тем чаще, хоть миллион

[Сергей Соколов]

l4m3r, не поняли идею. Сумма всех весов равна 100% вероятностей. Остается пропорционально разложить один исход за другим

[l4m3r]

Сергей Соколов, это вы не поняли. Я не так выразился, извините. Это не веса, получается. Не знаю как назвать. Чем цифра больше, тем чаще выпадает. Грубо говоря может быть так:

$a = [
     'a' => 55,
     'b' => 123123,
     'f' => 0.0000005,
// ...
];

[Сергей Соколов]

l4m3r, я именно так и понял. Упростим: всего 2 варианта, у одного вес 99, у другого 1.
Выбрасывайте равномерно слусайное число от 1 до 100. Если выпало 1-99, вариант а. Если выпало 100, вар. б.

[l4m3r]

Сергей Соколов, я только утром на свежую голову понял, что вы все верно написали)

Answer 2

[Дмитрий]

А я бы все веса поделил на наименьшее из них (N_i = вес_i / вес_min), и с полученными значениями N_i создал бы массив из букв, где каждая повторяется N_i количество раз.

А далее или перемешал бы его, или брал бы из него случайным образом очередную букву

Comments

[l4m3r]

Господи, ты гений

[Дмитрий]

l4m3r, тут есть нюанс, могут попасться такие веса, что в результате деления получим дробное значение, Например: если 'b' => 0.05, а 'f' => 0.00000011, то N_b не будет целым. Тогда надо смотреть по потребностям в точности, и либо попросту округлять, либо вводить общий для всех множитель, дабы привести все N_i к целым значениям. Это отдельная задача (решение крутится в голове). Если нужно, пиши, я подумаю.

[Андрей]

Можно, в принципе, и не перемешивать...

[Андрей]

Но из-за коэффициента f там будут десятки миллионов записей, так-что надо подумать еще... Это решение не эффективно по памяти.

[Дмитрий]

Андрей, я тоже думал, что будет огромный массив - но тут опять же важно знать, сколько всего элементов в массиве $a, в каком диапазоне (с каким разбросом) и с какой точностью нужно придерживаться заданного распределения. Решений может быть несколько и разработчик должен выбрать оптимальное в данной конкретной ситуации. Когда же это просто тестовое задание... Эх!

А что касается

Можно, в принципе, и не перемешивать...

я же писал, или-или: либо перемешать и брать по очереди, либо не перемешивать и выбирать случайное значение... Но я вроде бы понял суть Вашего подхода - конечно же, он лишён недостатков громоздкости по памяти.

[Андрей]

Справедливости ради скажу, что первым делом я тоже про массив подумал, но потом увидел коэффициент 'f' => 0.0000005, прикинул во сколько его нужно умножить, чтобы получить единицу, т.е. 2000000 (2 млн), прикинул, что это далеко не предел, и стал думать, как сделать то же самое, но без массива. :)

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

Answer 3

[Андрей]

Приводим коэффициенты к целым числам пропорционально так, чтобы минимальный коэффициент равнялся единице, остальные округляем до единиц. Таким образом получаем на выходе массив с целыми числами, где отношения в пропорции элементов друг к другу будут близкими к изначальным. Далее на основе этого промежуточного массива генерируем новый, с диапазонами, для первого элемента от 0 до его значения, для каждого последующего от суммы всех предыдущих значений до сумма + текущее значение. Таким образом весь массив диапазонами покрывает значения от 0 до суммы всех величин из первого промежуточного массива, которую обозначим как S. Далее используем только второй массив с диапазонами, для каждого элемента выборки генерим рандомное число R от 0 до S, и находим ключ согласно тому диапазону, куда в каждой итерации попадает R.

По идее данный алгоритм идентичен варианту Дмитрия, но эффективен по части использования памяти. Опять же, его тоже можно оптимизировать. :)

ЗЫ: Те же яйца, но в профиль предложил Сергей Соколов

Comments

[l4m3r]

Где ты раньше был :) Это было часть тестового задания на одно из собес. Но в итоге отправил уже неэффективное по памяти. Я может быть и сам допер, но времени оставалось мало

[Андрей]

Сорян, я почту проверяю когда свободная минутка выдается. :)