Muestra aleatoria ponderada en python

Estoy buscando una definición razonable de una funciónweighted_sample eso no devuelve solo un índice aleatorio para una lista de pesos dados (que sería algo así 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 una distribución categórica con pesos constantes) pero una muestra aleatoria dek de aquellos,sin reemplazo, Tal comorandom.sample se comporta en comparación conrandom.choice.

Tal comoweighted_choice Se puede escribir como

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

weighted_sample podría ser escrito como

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

pero me gustaría una solución que no me obligue a desentrañar los pesos en una lista (posiblemente enorme).

Edición: si hay algoritmos agradables que me devuelvan un histograma / lista de frecuencias (en el mismo formato que el argumentoweights) en lugar de una secuencia de índices, eso también sería muy útil.