(Python) алгоритм случайного выбора ключа на основе пропорциональности / веса

Question

Я немного растерялся, как найти чистый алгоритм для выполнения следующих действий:

Предположим, у меня есть диктант k:

>>> k = {'A': 68, 'B': 62, 'C': 47, 'D': 16, 'E': 81}

Теперь я хочу выбрать один из этих ключей случайным образом, исходя из «веса», который они имеют в общем (т. Е. Сумме) количестве ключей.

>>> sum(k.values()) 
>>> 274

Так что есть

>>> 68.0/274.0
>>> 0.24817518248175183

Изменение на 24,81% при выборе A.

Как бы вы написали алгоритм, который позаботится об этом? Другими словами, это гарантирует, что при 10000 случайных пиков A будет выбираться 2,481 раза?

Answer 1

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

import random

def WeightedPick(d):
    r = random.uniform(0, sum(d.itervalues()))
    s = 0.0
    for k, w in d.iteritems():
        s += w
        if r < s: return k
    return k

def Test():
    k = {'A': 68, 'B': 62, 'C': 47, 'D': 16, 'E': 81}
    results = {}
    for x in xrange(10000):
        p = WeightedPick(k)
        results[p] = results.get(p, 0) + 1
    print results

Test()

Answer 2

Это должно сработать:

>>> k = {'A': 68, 'B': 62, 'C': 47, 'D': 16, 'E': 81}
>>> import random
>>> def weighted_pick(dic):
...     total = sum(dic.itervalues())
...     pick = random.randint(0, total-1)
...     tmp = 0
...     for key, weight in dic.iteritems():
...         tmp += weight
...         if pick < tmp:
...             return key

Answer 3

нужно также посмотреть на эта ссылка

составьте два списка для k, скажем xk и yk

from scipy import stats
custm = stats.rv_discrete(name='test', values=(xk, yk))
custm.rvs(size=1)

Answer 4

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

import random
d = {'A': 68, 'B': 62, 'C': 47, 'D': 16, 'E': 81}
s = ''.join(k*v for k,v in d.items())
random.choice(s)

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

Answer 5

Алгоритм будет такой ..

Выберите случайным образом число от 1 до 274. Для этого вызовите функцию rand () (предположим, она возвращает значение от 0 до 1), умножьте rand () на 274. Полученное значение должно теперь находиться в диапазоне , Если между 1 и 68, выберите A, если между 69 и 130 выберите B и так далее. Таким образом, ваша вероятность остается в живых, и ваша операция успешна.

PS: я парень из Java, не знаю синтаксис Python.

Answer 6

Я разработал алгоритм несколько лет назад, с применением в Perl и SQL, вы можете прочитать о нем здесь , в комплекте с анализом и проверками, почему он (скорее всего) является правильным.

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

Эта функция:

x[i] = -log(1 - rand())/weight[i]