Взвешенная версия random.choice

 def weighted_choice(choices): total = sum(w for c, w in choices) r = random.uniform(0, total) upto = 0 for c, w in choices: if upto + w >= r: return c upto += w assert False, "Shouldn't get here" 

Начиная с версии 1.7.0, NumPy имеет функцию choice которая поддерживает распределения вероятностей.

 from numpy.random import choice draw = choice(list_of_candidates, number_of_items_to_pick, p=probability_distribution) 

Обратите внимание, что list_of_candidates представляет собой последовательность в том же порядке list_of_candidates . Вы также можете использовать ключевое слово replace=False чтобы изменить поведение, чтобы нарисованные элементы не были заменены.

1. Упорядочить веса в кумулятивное распределение.
2. Используйте random.random (), чтобы выбрать случайный float 0.0 <= x < total .
3. Найдите распределение, используя bisect.bisect, как показано в примере на странице http://docs.python.org/dev/library/bisect.html#other-examples .

 from random import random from bisect import bisect def weighted_choice(choices): values, weights = zip(*choices) total = 0 cum_weights = [] for w in weights: total += w cum_weights.append(total) x = random() * total i = bisect(cum_weights, x) return values[i] >>> weighted_choice([("WHITE",90), ("RED",8), ("GREEN",2)]) 'WHITE' 

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

Итак, с Python3.6 есть choices метода из random модуля.

 Python 3.6.1 (v3.6.1:69c0db5050, Mar 21 2017, 01:21:04) Type 'copyright', 'credits' or 'license' for more information IPython 6.0.0 -- An enhanced Interactive Python. Type '?' for help. In [1]: import random In [2]: population = [['a','b'], ['b','a'], ['c','b']] In [3]: list_of_prob = [0.2, 0.2, 0.6] In [4]: population = random.choices(population, weights=list_of_prob, k=10) In [5]: population Out[5]: [['c', 'b'], ['c', 'b'], ['b', 'a'], ['c', 'b'], ['c', 'b'], ['b', 'a'], ['c', 'b'], ['b', 'a'], ['c', 'b'], ['c', 'b']] 

И люди также упомянули, что есть numpy.random.choice которые поддерживают весы, НО это не поддерживает 2d массивы и так далее.

Итак, в основном вы можете получить все, что хотите, с помощью random.choices если у вас есть 3.6.x Python.

Если вы не против использования numpy, вы можете использовать numpy.random.choice .

Например:

 import numpy items = [["item1", 0.2], ["item2", 0.3], ["item3", 0.45], ["item4", 0.05] elems = [i[0] for i in items] probs = [i[1] for i in items] trials = 1000 results = [0] * len(items) for i in range(trials): res = numpy.random.choice(items, p=probs) #This is where the item is selected! results[items.index(res)] += 1 results = [r / float(trials) for r in results] print "item\texpected\tactual" for i in range(len(probs)): print "%s\t%0.4f\t%0.4f" % (items[i], probs[i], results[i]) 

Если вы знаете, сколько вариантов вам нужно сделать заранее, вы можете сделать это без цикла:

 numpy.random.choice(items, trials, p=probs) 

Сырой, но может быть достаточно:

 import random weighted_choice = lambda s : random.choice(sum(([v]*wt for v,wt in s),[])) 

Это работает?

 # define choices and relative weights choices = [("WHITE",90), ("RED",8), ("GREEN",2)] # initialize tally dict tally = dict.fromkeys(choices, 0) # tally up 1000 weighted choices for i in xrange(1000): tally[weighted_choice(choices)] += 1 print tally.items() 

Печать:

 [('WHITE', 904), ('GREEN', 22), ('RED', 74)] 

Предполагается, что все веса являются целыми числами. Им не нужно добавлять до 100, я просто сделал это, чтобы облегчить интерпретацию результатов теста. (Если веса являются числами с плавающей запятой, умножьте их на 10 раз, пока все веса> = 1.)

 weights = [.6, .2, .001, .199] while any(w < 1.0 for w in weights): weights = [w*10 for w in weights] weights = map(int, weights) 

Если у вас есть взвешенный словарь вместо списка, вы можете написать это

 items = { "a": 10, "b": 5, "c": 1 } random.choice([k for k in items for dummy in range(items[k])]) 

Обратите внимание, что [k for k in items for dummy in range(items[k])] создает этот список ['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'c', 'b', 'b', 'b', 'b', 'b']

Вот версия, которая включена в стандартную библиотеку для Python 3.6:

 import itertools as _itertools import bisect as _bisect class Random36(random.Random): "Show the code included in the Python 3.6 version of the Random class" def choices(self, population, weights=None, *, cum_weights=None, k=1): """Return ak sized list of population elements chosen with replacement. If the relative weights or cumulative weights are not specified, the selections are made with equal probability. """ random = self.random if cum_weights is None: if weights is None: _int = int total = len(population) return [population[_int(random() * total)] for i in range(k)] cum_weights = list(_itertools.accumulate(weights)) elif weights is not None: raise TypeError('Cannot specify both weights and cumulative weights') if len(cum_weights) != len(population): raise ValueError('The number of weights does not match the population') bisect = _bisect.bisect total = cum_weights[-1] return [population[bisect(cum_weights, random() * total)] for i in range(k)] 

Источник: https://hg.python.org/cpython/file/tip/Lib/random.py#l340

Начиная с Python v3.6 , random.choices можно использовать для возврата list элементов заданного размера из данной группы с дополнительными весами.

random.choices(population, weights=None, *, cum_weights=None, k=1)

• население : list содержащий уникальные наблюдения. (Если пусто, вызывает IndexError )

• вес : более точно относительные веса, необходимые для выбора.

• cum_weights : совокупный вес, необходимый для выбора.

• k : размер ( len ) list должен быть выведен. (По умолчанию len()=1 )

Немного оговорок:

1) Он использует взвешенную выборку с заменой, поэтому нарисованные элементы будут позже заменены. Значения в последовательности весов сами по себе не имеют значения, но их относительное отношение действительно.

В отличие от np.random.choice который может принимать только вероятности в виде весов и также должен обеспечивать суммирование индивидуальных вероятностей до 1 критерия, здесь нет таких правил. Пока они относятся к числовым типам ( int/float/fraction except Decimal type), они все равно будут выполняться.

 >>> import random # weights being integers >>> random.choices(["white", "green", "red"], [12, 12, 4], k=10) ['green', 'red', 'green', 'white', 'white', 'white', 'green', 'white', 'red', 'white'] # weights being floats >>> random.choices(["white", "green", "red"], [.12, .12, .04], k=10) ['white', 'white', 'green', 'green', 'red', 'red', 'white', 'green', 'white', 'green'] # weights being fractions >>> random.choices(["white", "green", "red"], [12/100, 12/100, 4/100], k=10) ['green', 'green', 'white', 'red', 'green', 'red', 'white', 'green', 'green', 'green'] 

2) Если не указаны ни веса, ни cum_weights , выбор производится с равной вероятностью. Если задана последовательность весов , она должна быть такой же длины, как и последовательность популяции .

Задание как весов, так и cum_weights вызывает TypeError .

 >>> random.choices(["white", "green", "red"], k=10) ['white', 'white', 'green', 'red', 'red', 'red', 'white', 'white', 'white', 'green'] 

3) cum_weights обычно являются результатом itertools.accumulate функции, которые действительно удобны в таких ситуациях.

_{Из связанной документации:}

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

Таким образом, либо поставка weights=[12, 12, 4] либо cum_weights=[12, 24, 28] для нашего надуманного случая дает один и тот же результат, а последний, кажется, более быстрый / эффективный.

Я бы потребовал сумму выборов 1, но это все равно работает

 def weightedChoice(choices): # Safety check, you can remove it for c,w in choices: assert w >= 0 tmp = random.uniform(0, sum(c for c,w in choices)) for choice,weight in choices: if tmp < weight: return choice else: tmp -= weight raise ValueError('Negative values in input') 

Общее решение:

 import random def weighted_choice(choices, weights): total = sum(weights) treshold = random.uniform(0, total) for k, weight in enumerate(weights): total -= weight if total < treshold: return choices[k] 

 import numpy as np w=np.array([ 0.4, 0.8, 1.6, 0.8, 0.4]) np.random.choice(w, p=w/sum(w)) 

Возможно, я слишком поздно внес что-либо полезное, но вот простой, короткий и очень эффективный фрагмент:

 def choose_index(probabilies): cmf = probabilies[0] choice = random.random() for k in xrange(len(probabilies)): if choice <= cmf: return k else: cmf += probabilies[k+1] 

Не нужно сортировать свои вероятности или создавать вектор с вашим cmf, и он прекращается, как только он находит свой выбор. Память: O (1), время: O (N), со средним временем работы ~ N / 2.

Если у вас есть веса, просто добавьте одну строку:

 def choose_index(weights): probabilities = weights / sum(weights) cmf = probabilies[0] choice = random.random() for k in xrange(len(probabilies)): if choice <= cmf: return k else: cmf += probabilies[k+1] 

Если ваш список взвешенных вариантов относительно статичен и вам нужна частая выборка, вы можете сделать один шаг предварительной обработки O (N), а затем сделать выбор в O (1), используя функции в этом связанном ответе .

 # run only when `choices` changes. preprocessed_data = prep(weight for _,weight in choices) # O(1) selection value = choices[sample(preprocessed_data)][0] 

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

 import random import bisect try: range = xrange except: pass def weighted_choice(choices): total, cumulative = 0, [] for c,w in choices: total += w cumulative.append((total, c)) r = random.uniform(0, total) # return index return bisect.bisect(cumulative, (r,)) # return item string #return choices[bisect.bisect(cumulative, (r,))][0] # define choices and relative weights choices = [("WHITE",90), ("RED",8), ("GREEN",2)] tally = [0 for item in choices] n = 100000 # tally up n weighted choices for i in range(n): tally[weighted_choice(choices)] += 1 print([t/sum(tally)*100 for t in tally]) 

Вот еще одна версия weighted_choice, которая использует numpy. Перейдите в вектор весов, и он вернет массив из 0, содержащий 1, указывающий, какой бункер выбран. В коде по умолчанию используется только однократная ничья, но вы можете передать количество ничьих, которые будут сделаны, и будет возвращено количество отсчетов на извлеченный бит.

Если вектор весов не суммируется с 1, он будет нормализован так, чтобы он выполнялся.

 import numpy as np def weighted_choice(weights, n=1): if np.sum(weights)!=1: weights = weights/np.sum(weights) draws = np.random.random_sample(size=n) weights = np.cumsum(weights) weights = np.insert(weights,0,0.0) counts = np.histogram(draws, bins=weights) return(counts[0])