Возвращение случайного значения из массива с вероятностью, пропорциональной его значению

Question

У меня есть массив типа

$keywords = array('apple'=>10,'orange'=>2,'grape'=>12); 

Я хочу случайным образом выбрать один из «ключей» из массива.Однако распределение вероятностей должно быть таким, чтобы вероятность выбора элемента была пропорциональна его значению.

Answer 1

Добавьте все значения (10 + 2 + 12 - 24); получить случайное число в диапазоне [0, 24) и выбрать соответствующий элемент в зависимости от того, лежит ли число в [0, 10), [10, 12) или [12, 24).

Answer 2

Я бы сделал это так:

    $probabilities = array('apple'=>50, 'orange'=>20, 'banana'=>10);

    function random_probability($probabilities) {
      $rand = rand(0, array_sum($probabilities));
      do {
        $sum = array_sum($probabilities);
        if($rand <= $sum && $rand >= $sum - end($probabilities)) {
          return key($probabilities);
        }
      } while(array_pop($probabilities));
    }

Answer 3

Подход O (log (n)) (он извлечен непосредственно из ответа на очень похожий вопрос ):

Обычная техника - преобразовать массив в массив кумулятивных сумм:

 [10 60 5 25]  --> [10 70 75 100]

Выберите случайное число в диапазоне от нуля до совокупной суммы (в примере: 0 <= x < 100). Затем используйте bisection на накопительном массиве, чтобы найти индекс в исходном массиве:

Random variable x      Index in the Cumulative Array      Value in Original Array
-----------------      -----------------------------      ----------------------
 0 <= x < 10                      0                            10
10 <= x < 70                      1                            60
70 <= x < 75                      2                             5
75 <= x < 100                     3                            25 

Например, если случайная величина x равна 4, разделив кумулятивный массив, вы получите индекс позиции 0, который соответствует 10 в исходном массиве.

И, если случайная величина x равна 72, деление пополам совокупного массива дает индекс позиции 2, который соответствует 5 в исходном массиве.