Ответ 1

Вычислить дискретную кумулятивную функцию плотности (CDF) вашего списка - или, проще говоря, массив суммарных сумм весов. Затем создайте случайное число в диапазоне от 0 до суммы всех весов (может быть 1 в вашем случае), выполните двоичный поиск, чтобы найти это случайное число в вашем дискретном массиве CDF и получить значение, соответствующее этой записи - это ваше взвешенное случайное число.

Ответ 2

Алгоритм прямой

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

Ответ 3

Пример в 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 greater than the random number
r = rand
selected = a.find{ |e,w| w>r }

p selected[0]

Ответ 4

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

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

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

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

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

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

Ответ 5

Другой пример ruby:

def weighted_rand(weights = {})
  raise 'Probabilities must sum up to 1' unless weights.values.inject(&:+) == 1.0

  u = 0.0
  ranges = Hash[weights.map{ |v, p| [u += p, v] }]

  u = rand
  ranges.find{ |p, _| p > u }.last
end

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

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

weighted_rand weights

Что ожидать:

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

Ответ 6

Я нашел эту статью, чтобы быть наиболее полезной при понимании этой проблемы полностью. fooobar.com/questions/50791/... также может быть тем, что вы ищете.

Я считаю, что оптимальным решением является использование Alias ​​Method (wikipedia). Требуется O (n) время для инициализации, O (1) время для выбора и O (n) памяти.

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

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

Инициализация:

• Создание массивов Alias ​​и Prob, каждый из которых n.
• Создайте два рабочих листа: Small и Large.
• Умножьте каждую вероятность на n.
• Для каждой масштабированной вероятности p _i:
  • Если p _i < 1, добавьте я в Small.
  • В противном случае (p _i ≥ 1) добавьте я в Large.
• Пока малые и большие не пустые: (сначала может быть опустели крупные объекты)
  • Удалить первый элемент из Small; назовите его l.
  • Удалить первый элемент из Large; назовите его g.
  • Set Prob [l] = p _l.
  • Установить псевдоним [l] = g.
  • Установите p _g: = (p _g + p _l) - 1. (Это более стабильный вариант.)
  • Если p _g < 1, добавьте g к Small.
  • В противном случае (p _g ≥ 1) добавьте g в Large.
• Пока Large не пуст:
  • Удалить первый элемент из Large; назовите его g.
  • Set Prob [g] = 1.
• Пока Small не пуст: это возможно только из-за численной нестабильности.
  • Удалить первый элемент из Small; назовите его l.
  • Set Prob [l] = 1.

Генерация:

• Сгенерируйте сверло для сверления с n-сторонней матрицы; вызовите сторону i.
• Переверните смещенную монету, которая приходит с головами с вероятностью Prob [i].
• Если монета появляется "голова", верните i.
• В противном случае верните Alias ​​[i].

Ответ 7

Решение 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]]

Ответ 8

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

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

Ответ 9

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

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

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

Ответ 10

Это код 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;
        }
    }
}

Ответ 11

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

В других терминах:

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

если 0.0 >= x < 0.2: Пункт 1

если 0,2 >= x < 0,8: Пункт 2

если 0,8 >= x < 1.0: Пункт 3

Ответ 12

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

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

У него есть некоторые недостатки.

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

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

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

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

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

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

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

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

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

элемент 1 отображается в 20% случаев. элемент 2 показывает 0,40% времени и имеет наивысшую вероятность.

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

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