алгоритм прямо вперед

rand_no = rand(0,1)
for each element in array 
     if(rand_num < element.probablity)
          select and break
     rand_num = rand_num - element.probability

пример в ruby

#each element is associated with its probability
a = {1 => 0.25 ,2 => 0.5 ,3 => 0.2, 4 => 0.05}

#at some point, convert to ccumulative probability
acc = 0
a.each { |e,w| a[e] = acc+=w }

#to select an element, pick a random between 0 and 1 and find the first   
#cummulative probability that's greater than the random number
r = rand
selected = a.find{ |e,w| w>r }

p selected[0]

Это можно сделать в O (1) ожидаемое время на образец следующим образом.

вычислить CDF F (i) для каждого элемента i как сумму вероятностей, меньших или равных i.

определить диапазон r(i) элемента i как интервал [F(i - 1), F (i)].

для каждого интервала [(i - 1)/n, i/n] создайте блок, состоящий из списка элементов, диапазон которых перекрывает интервал. Это занимает O (n) времени в общей сложности для всего массива, пока вы разумно осторожный.

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

стоимость выборки равна O (ожидаемая длина случайно выбранного списка)

Я нашел в этой статье чтобы быть наиболее полезным при полном понимании этой проблемы. этот вопрос stackoverflow также может быть то, что вы ищете.

---

Я считаю, что оптимальным решением является использование метод псевдонима (Википедия). Это требует O (n) время инициализации O (1) время сделать выбор, и O (n) память.

вот алгоритм для генерации результат прокатки взвешенный n-односторонний штамп (отсюда тривиально выбрать элемент из длины -n массив), как брать от в этой статье. Автор предполагает, что у вас есть функции для прокатки справедливого штампа (floor(random() * n)) и переворачивание предвзятой монеты (random() < p).

алгоритм: метод псевдонима Vose

инициализации:

1. создать массивы псевдоним и Prob, каждый в размере n.
2. создать два рабочих списков, маленький и большой.
3. умножьте каждую вероятность на n.
4. для каждой масштабируемой вероятности p_я:
   1. если p_я добавьте я до маленький.
   2. в противном случае (p_я ≥ 1), добавить я до большой.
5. пока маленький и большой не пусты: (большой может быть опорожнена в первую очередь)
   1. удалить первый элемент маленький; называют его l.
   2. удалить первый элемент большой; называют его g.
   3. Set Prob[l]=p_l.
   4. Set псевдоним[l]=g.
   5. Set p_g : = (p_g+p_l) -1. (Это более численно стабильный вариант.)
   6. если p_g добавьте g до маленький.
   7. в противном случае (p_g ≥ 1), добавить g to большой.
6. пока большой не пуст:
   1. удалить первый элемент большой; называют его g.
   2. Set Prob[g] = 1.
7. пока маленький не пуст: это возможно только из-за численной неустойчивости.
   1. удалить первый элемент маленький; назовем его l.
   2. Set Prob[l] = 1.

поколение:

1. создайте справедливый рулон штампа из n-односторонний умереть; вызов стороны я.
2. переверните предвзятую монету, которая появляется с вероятностью Prob[i].
3. если монета всплывает "Орел", верните я.
4. в противном случае, возвращение псевдоним[i].

другой пример Ruby:

def weighted_rand(weights = {})
  raise 'Probabilities must sum up to 1' unless weights.values.inject(&:+) == 1.0
  raise 'Probabilities must not be negative' unless weights.values.all? { |p| p >= 0 }
  # Do more sanity checks depending on the amount of trust in the software component using this method
  # E.g. don't allow duplicates, don't allow non-numeric values, etc.

  # Ignore elements with probability 0
  weights = weights.reject { |k, v| v == 0.0 }   # e.g. => {"a"=>0.4, "b"=>0.4, "c"=>0.2}

  # Accumulate probabilities and map them to a value
  u = 0.0
  ranges = weights.map { |v, p| [u += p, v] }   # e.g. => [[0.4, "a"], [0.8, "b"], [1.0, "c"]]

  # Generate a (pseudo-)random floating point number between 0.0(included) and 1.0(excluded)
  u = rand   # e.g. => 0.4651073966724186

  # Find the first value that has an accumulated probability greater than the random number u
  ranges.find { |p, v| p > u }.last   # e.g. => "b"
end

как использовать:

weights = {'a' => 0.4, 'b' => 0.4, 'c' => 0.2, 'd' => 0.0}

weighted_rand weights

чего ожидать:

d = 1000.times.map{ weighted_rand weights }
d.count('a') # 396
d.count('b') # 406
d.count('c') # 198

Ruby решение с помощью самовывоз:

require 'pickup'

chances = {0=>80, 1=>20}
picker = Pickup.new(chances)

пример:

5.times.collect {
  picker.pick(5)
}

дал выход:

[[0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0], 
 [0, 0, 0, 1, 1], 
 [0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 1]]

если массив мал, я бы дал массиву длину, в данном случае, пять и назначил соответствующие значения:

array[
    0 => 0
    1 => 0
    2 => 0
    3 => 0
    4 => 1
]

Это PHP код, который я использовал в производстве:

/**
 * @return \App\Models\CdnServer
*/
protected function selectWeightedServer(Collection $servers)
{
    if ($servers->count() == 1) {
        return $servers->first();
    }

    $totalWeight = 0;

    foreach ($servers as $server) {
        $totalWeight += $server->getWeight();
    }

    // Select a random server using weighted choice
    $randWeight = mt_rand(1, $totalWeight);
    $accWeight = 0;

    foreach ($servers as $server) {
        $accWeight += $server->getWeight();

        if ($accWeight >= $randWeight) {
            return $server;
        }
    }
}

трюк может заключаться в выборке вспомогательного массива с повторениями элементов, которые отражают вероятность

учитывая элементы, связанные с их вероятностью, в процентах:

h = {1 => 0.5, 2 => 0.3, 3 => 0.05, 4 => 0.05 }

auxiliary_array = h.inject([]){|memo,(k,v)| memo += Array.new((100*v).to_i,k) }   

ruby-1.9.3-p194 > auxiliary_array 
 => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,                                 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4] 

auxiliary_array.sample

Если вы хотите быть как можно более общим, вам нужно рассчитать множитель на основе максимального количества дробных цифр и использовать его вместо 100:

m = 10**h.values.collect{|e| e.to_s.split(".").last.size }.max

Я бы предположил, что числа больше или равны 0,8, но меньше 1,0 выбирает третий элемент.

другими словами:

x-случайное число от 0 до 1

Если 0.0 > = x

Если 0.2 > = x

Если 0.8 > = x

Я собираюсь улучшить https://stackoverflow.com/users/626341/masciugo ответьте.

в основном вы делаете один большой массив, где, сколько раз элемент появляется пропорционально весу.

Он имеет некоторые недостатки.

1. вес не может быть целым числом. Представьте, что элемент 1 имеет вероятность pi, а элемент 2 имеет вероятность 1-pi. Как вы это делите? Или представьте себе если сотни таких элементы.
2. созданный массив может быть очень большой. Представьте, что если наименьший общий множитель равен 1 миллиону, то нам понадобится массив из 1 миллиона элементов в массиве, который мы хотим выбрать.

чтобы противостоять этому, это то, что вы делаете.

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

затем выбрать случайный элемент из обычного.

Так что если есть 3 элементы с разным весом, вы просто выбираете элемент из массива 1-3 элементов.

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

в этом случае я предлагаю, чтобы вероятность вставки элемента была p(inserted)=wi/wmax.

таким образом, будет вставлен один элемент, а именно тот, который имеет наибольшую вероятность. Другой элемент будет вставлена относительная вероятность.

скажем, у нас есть 2 объекта.

появляется элемент 1 .20% времени. появляется элемент 2 .40% времени и имеет самую высокую вероятность.

в thearray элемент 2 будет отображаться все время. Элемент 1 будет отображаться в половине случаев.

таким образом, элемент 2 будет называться в 2 раза больше, чем элемент 1. Для общности все остальные элементы будут называться пропорциональными их весу. Также сумма всех их вероятность-это 1, потому что массив всегда будет иметь по крайней мере 1 элемент.