Ich suche eine vernünftige Definition einer Funktionweighted_sample das gibt nicht nur einen zufälligen Index für eine Liste gegebener Gewichte zurück (das wäre so etwas wie

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")

eine kategoriale Verteilung mit konstanten Gewichten zu geben), aber eine Zufallsstichprobe vonk von diesen,ohne Ersatz, genauso wierandom.sample verhält sich im Vergleich zurandom.choice.

Genauso wieweighted_choice kann geschrieben werden als

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

weighted_sample könnte geschrieben werden als

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

aber ich möchte eine Lösung, bei der ich die Gewichte nicht in eine (möglicherweise riesige) Liste zerlegen muss.

Edit: Wenn es irgendwelche netten Algorithmen gibt, die mir ein Histogramm / eine Liste von Frequenzen zurückgeben (im selben Format wie das Argument)weights) anstelle einer Folge von Indizes wäre das auch sehr nützlich.