Eu estou procurando uma definição razoável de uma funçãoweighted_sample que não retorna apenas um índice aleatório para uma lista de pesos dados (o que seria algo como

def weighted_choice(weights, random=random):
    """ Given a list of weights [w_0, w_1, ..., w_n-1],
        return an index i in range(n) with probability proportional to w_i. """
    rnd = random.random() * sum(weights)
    for i, w in enumerate(weights):
        if w<0:
            raise ValueError("Negative weight encountered.")
        rnd -= w
        if rnd < 0:
            return i
    raise ValueError("Sum of weights is not positive")

para dar uma distribuição categórica com pesos constantes), mas uma amostra aleatória dek daqueles,Sem substituição, assim comorandom.sample se comporta em comparação comrandom.choice.

Assim comoweighted_choice pode ser escrito como

lambda weights: random.choice([val for val, cnt in enumerate(weights)
    for i in range(cnt)])

weighted_sample poderia ser escrito como

lambda weights, k: random.sample([val for val, cnt in enumerate(weights)
    for i in range(cnt)], k)

mas eu gostaria de uma solução que não me obrigue a desvendar os pesos em uma lista (possivelmente enorme).

Edit: Se houver algum algoritmo legal que me devolva um histograma / lista de freqüências (no mesmo formato do argumento)weights) em vez de uma sequência de índices, isso também seria muito útil.