Случайный взвешенный выбор

Ответ 1

Создайте кумулятивную функцию распределения для каждого ID1, таким образом:

cdfs = defaultdict()
for id1,id2,val in d:
    prevtotal = cdfs[id1][-1][0]
    newtotal = prevtotal + val
    cdfs[id1].append( (newtotal,id2) )

Итак, у вас будет

cdfs = { 701 : [ (0.2,1), (0.5,2), (1.0,3) ], 
         702 : [ (0.2,1), (0.5,2) ],
         703 : [ (0.5,3) ] }

Затем создайте случайное число и найдите его в списке.

def func(id1):
    max = cdfs[id1][-1][0]
    rand = random.random()*max
    for upper,id2 in cdfs[id1]:
        if upper>rand:
            return id2
    return None

Ответ 2

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

def func(id):
    rnd = random()
    sum = 0
    for row in d:
        if row[0] == id:
            sum = sum + row[2]
            if rnd < sum:
                return row[1]

В примере данных из OP это выглядит следующим образом:

• Выберите случайное число от 0 до 1.0
• Если число < 0.2 возвращает первый элемент
• Если номер < 0.5 возвращает второй элемент
• Else (если число < 1.0) возвращает третий элемент

Ответ 3

Используйте дискретное равномерное распределение из случайного модуля над достаточным количеством значений, затем разделите его:

Например, для случая 701 используйте распределение по 10 значениям, для 2 значений возвратите 1, для другого 3, возврата 2 и для остальных 5 верните 3.

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

Ответ 4

Если ваши процентные значения не будут точнее, чем целые проценты, используйте генератор случайных чисел для генерации числа 0-99.

Затем в вашей функции используйте (программные) случаи, чтобы выбрать правильный номер. Например (очистить это):

if 701
  if random_num < 20
    return 1
  else if random number < 50   // ( 20 + 30 )
    return 2
  else if random number < 100  // ( 20 + 30 + 50 )
    return 3
  else
    // error

Ответ 5

Очень быстрый взлом:

import random

d = {
    701: [(1,0.2),(2,0.3),(3,0.5)],
    702: [(1,0.2),(2,0.3),(3,0.5)]
}

def func(value):
    possible_values=d[value]
    total=sum(p[-1] for p in possible_values)
    random_value=random.random()
    prob=possible_values[0][-1]/total
    index=1
    while index<len(possible_values) and prob<random_value:
        prob+=possible_values[index][-1]/total
        index+=1
    return possible_values[index-1][0]

if __name__=='__main__':
    testcases=1000
    cnt=[0,0,0]
    for case in xrange(testcases):
        answer=func(701)
        cnt[answer-1]+=1
    for i in xrange(3):
        print "Got %d %f%% of the time"%(i+1,float(cnt[i])/testcases*100)

Это некрасиво, но это первое, что пришло в голову, и, похоже, работает так, как ожидалось.

Это делается для получения случайного значения в интервале [0,1) (с использованием random.random()). Затем он использует, попадает ли случайное значение в интервалы [0,0,2), [0,2,0,5) или [0,5,1), чтобы выяснить, какое значение вернуть.

Ответ 6

Две идеи (позвольте мне проиллюстрировать это отдельными параметрами и соотношениями для ясности в именах аргументов, если они упакованы в кортеж, вы можете сохранить "zip" ):

a) Денормализовать веса, чтобы получить целые отношения, затем поместить в список столько копий, сколько отношение, и использовать random.choice.

def choice_with_ratios(options, ratios):
    tmp = sum([[v]*n for v, n in zip(options, ratios)], [])
    return random.choice(tmp)

b) Используйте нормализованные веса и начинайте суммирование до тех пор, пока не достигнете произвольно сгенерированного однородного значения

def choice_with_weights(options, weights):
    s = 0
    r = random.random()
    for v, w in zip(options, weights):
        s += w
        if s >= r: break
    return v

Кстати, если первое поле используется как ключ, вы должны иметь его в словаре, например:

d = {
  701: ((1, 0.2), (2, 0.3), (3, 0.5),
  702: ((1, 0.3), (2, 0.2), (3, 0.5)
}

Ответ 7

Вы также можете создать список из 100 элементов для каждого значения, а затем пусть random.choice делает выбор из списка посещенных, члены которого загружаются в желаемом весе:

import random
from collections import defaultdict

d = ( 
  (701, 1, 0.2), 
  (701, 2, 0.3), 
  (701, 3, 0.5), 
  (702, 1, 0.2), 
  (702, 2, 0.3), 
  (702, 3, 0.5) 
) 

class WeightedLookup(object):
    def __init__(self, valueTupleList):
        self.valdict = defaultdict(list)
        for key, val, prob in valueTupleList:
            self.valdict[key] += [val]*(int)(prob*100)

    def __getitem__(self,key):
        return random.choice(self.valdict[key])


lookup = WeightedLookup(d)

# test out our lookup distribution, sample it 100000 times
res = { 1:0, 2:0, 3:0 }
for i in range(100000):
    res[lookup[701]] += 1

# print how many times each value was returned
for k in (1,2,3):
    print k, res[k]

Печать

1 20059
2 30084
3 49857