Efficiently sampling from a multiset (Counter) in Python

Question

Annoyingly, the following doesn't work:

from collections import Counter
import random

c = Counter([1,1,1,1,0,0])
random.choice(c) # I expect this to return 1 with probability 2/3, 
                 # and 0 with probability 1/3.
                 # It actually returns 4 or 2, with probability 1/2

What is the idiomatic way to sample from a multiset in Python (any version)?

Edit yes, I do really need to use a multiset. My actual data is much bigger and just storing it in a list would not be practical.

Edit 2 I need to do this with a reasonable degree of efficiency, as my code will do this repeatedly. There will be a lot of data stored in the Counter object, and anything that involves copying all of this data into a new data structure is not going to be a viable solution.

Answer 1

From the docs:

A common task is to make a random.choice() with weighted probabilities.

If the weights are small integer ratios, a simple technique is to build a sample population with repeats:

>>> weighted_choices = [('Red', 3), ('Blue', 2), ('Yellow', 1), ('Green', 4)]
>>> population = [val for val, cnt in weighted_choices for i in range(cnt)]
>>> random.choice(population)
'Green'

A more general approach is to arrange the weights in a cumulative distribution with itertools.accumulate(), and then locate the random value with bisect.bisect():

>>> choices, weights = zip(*weighted_choices)
>>> cumdist = list(itertools.accumulate(weights))
>>> x = random.random() * cumdist[-1]
>>> choices[bisect.bisect(cumdist, x)]
'Blue'

For your application, you will probably want to use the Counter to build a list of choices and a list of cumulative probabilities, then sample with the second technique.