Как выбрать элемент в списке по определенной вероятности?

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

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

Существует изящный, но простой способ случайного выбора индексов в data в соответствии с распределением в probs, который известен как колесо рулетки. Я считаю, что в Python это должно выглядеть примерно так

import random

data = ['A', 'B', 'C', 'D']

probs = [0.2, 0.4, 0.3, 0.1]

def roulette_wheel(probs):
    rand = random.random()
    for slot, prob in enumerate(probs):
        rand -= prob
        if rand < 0.0:
            return slot

Обратите внимание, что это можно обобщить до списка неотрицательных весов (который не должен суммироваться до 1), умножив rand на член sum(weights). Мне кажется, я впервые увидел эту симпатичную идею в книге о программировании на Паскале несколько эонов назад.

Изменить:

Как предложил MadPhysicist в comment это можно сделать намного более эффективным, если нужно многократно использовать одни и те же данные. В этом случае можно предварительно вычислить кумулятивную функцию распределения, а затем просто выполнить двоичный поиск индекса так, чтобы cumulative prob. <= rand ~ U(0, 1). В Python это могло бы выглядеть, например, как-то так:

from random import random
from bisect import bisect_right


def cdf(probs):
    cdf = []
    total = 0.0
    for p in probs:
        total += p
        cdf.append(total)
    return cdf


def roulette_wheel_bisect(cdf):
    return bisect_right(cdf, random())

# compute cdf
cumsum = cdf(probs)

# randomly draw 10 indexes 
for i in range(0, 10):
    print(roulette_wheel_bisect(cumsum))

Отказ от ответственности: я не программист на Python по профессии, поэтому приведенный выше код должен только иллюстрировать общую идею. Это может быть не очень надежным для практического использования. Вы всегда должны использовать хорошо протестированную стандартную библиотеку, например, numpy, если можете.

Edit2:

Я только что узнал, что numpy имеет numpy.random. выбор, который сделает именно то, что вам нужно. Пример:

from numpy import random

data = ['A', 'B', 'C', 'D']
probs = [0.2, 0.4, 0.3, 0.1]

# randomly draw 10 list elements with replacement
for i in range(0, 10):
    print(random.choice(data, p=probs))