Фиксированный пропорциональный выбор

Question

У меня есть набор элементов, и мне нужно выбрать любой элемент из него. Каждый элемент связан с процентным шансом. Проценты добавляются до 100.

Мне нужно выбрать один из этих элементов, чтобы шансы выбора элемента равны процентному значению. Поэтому, если у элемента есть вероятность 25%, у него должно быть 25% шансов на выбор. Другими словами, если мы выбираем элементы в 1 мил раз, этот элемент следует выбирать примерно в 250 тыс. Раз.

Answer 1

То, что вы описываете, является многочленным процессом.

http://en.wikipedia.org/wiki/Multinomial_distribution#Sampling_from_a_multinomial_distribution

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

1. Сортировка в «коробки» в обратном порядке их вероятности: (. не нужно это просто оптимизация) так, что у вас есть, например, значений = [0.45,0.3,0.15,0.1]

2. затем создайте «кумулятивное» распределение, которое является суммой всех элементов с индексом < = i. псевдокод:

   cumulant=[0,0,0,0] // initiate it 
   s=0 
   for j=0 to size()-1 { 
       s=s+values[i] ; 
       cumulant[i]=s 
   } 
   

   в нашем случае кумулянта = [0.45,0.70,0.85, 1] ​​

3. сделать равномерное случайное число х между 0 и 1. Для PHP: http://php.net/manual/en/function.rand.php

4. полученный случайный индекс ящика i равен

   самый высокий i, для которого кумулянт [i] < x

псевдокод:

for j=0 to size()-1 { 
    if !(cumulant[i]<){ 
    print "your index is ",i 
    break; 
    } 

, что это. Получите еще один случайный индекс i, вернувшись к пункту 3.

, если вы отсортированы как указано выше, это означает, что окончательный поиск будет быстрее. Например, если у вас есть этот вектор вероятностей: 0,001 0,001 0,001 0,001 0,996, то при сортировке вам почти всегда придется смотреть только на индекс i = 0, так как случайное число x почти всегда будет ниже 0,996 , Если сортировка рассчитывается или нет, это зависит от того, используете ли вы одни и те же «боксы». Итак, да с 250 тыс. Попыток это очень поможет. Просто помните, что индекс ящика, который вы получаете, предназначен для отсортированного вектора.

Answer 2

Думаю, мне было быстрее написать это, чем вам, чтобы показать нам, что вы делали до сих пор.

Возможно, это не лучшее решение, но, поскольку оно стоит, похоже, что это единственное, что у вас есть.

Здесь вы идете:

$elements = array(
    'This' => 25, 
    'is' => 15, 
    'a' => 15, 
    'crappy' => 20, 
    'list' => 25 
); 

asort($elements); 
$elements = array_reverse($elements); 

// Precalc cumulative value 
$cumulant = 0; 
foreach ($elements as $key => &$value) { 
    $cumulant += $value; 
    $value = $cumulant; 
} 

function pickAnElement($elements) { 
    $random = rand(1, 100); 
    foreach ($elements as $key => $value) { 
     if ($random <= $value) { 
      return $key; 
     } 
    } 
} 

$picks = array(); 

for ($i = 0; $i < 10000; $i++) { 
    $element = pickAnElement($elements); 
    if (!array_key_exists($element, $picks)) { 
     $picks[$element] = 0; 
    } 
    $picks[$element]++; 
} 

var_dump($picks); 

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