(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%, что выбрано.

Как бы вы написали алгоритм, который позаботится об этом? Другими словами, это гарантирует, что при 10.000 случайных пиков 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

Алгоритм был бы такой..

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

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

Answer 4

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

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

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

Answer 5

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

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 6

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

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

Эта функция:

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