How can I get a weighted random pick from Python's Counter class?

Question

I have a program where I'm keeping track of the success of various things using collections.Counter — each success of a thing increments the corresponding counter:

import collections
scoreboard = collections.Counter()

if test(thing):
    scoreboard[thing]+ = 1

Then, for future tests, I want to skew towards things which have generated the most success. Counter.elements() seemed ideal for this, since it returns the elements (in arbitrary order) repeated a number of times equal to the count. So I figured I could just do:

import random
nextthing=random.choice(scoreboard.elements())

But no, that raises TypeError: object of type 'itertools.chain' has no len(). Okay, so random.choice can't work with iterators. But, in this case, the length is known (or knowable) — it's sum(scoreboard.values()).

I know the basic algorithm for iterating through a list of unknown length and fairly picking an element at random, but I suspect that there's something more elegant. What should I be doing here?

Answer 1

You can do this rather easily by using itertools.islice to get the Nth item of an iterable:

>>> import random
>>> import itertools
>>> import collections
>>> c = collections.Counter({'a': 2, 'b': 1})
>>> i = random.randrange(sum(c.values()))
>>> next(itertools.islice(c.elements(), i, None))
'a'

Answer 2

Given a dictionary of choices with corresponding relative probabilities (can be the count in your case), you can use the new random.choices added in Python 3.6 like so:

import random

my_dict = {
    "choice a" : 1, # will in this case be chosen 1/3 of the time
    "choice b" : 2, # will in this case be chosen 2/3 of the time
}

choice = random.choices(*zip(*my_dict.items()))[0]

For your code that uses Counter, you can do the same thing, because Counter also has the items() getter.

import collections
import random

my_dict = collections.Counter(a=1, b=2, c=3)
choice = random.choices(*zip(*my_dict.items()))[0]

Explanation: my_dict.items() is [('a', 1), ('b', 2), ('c', 3)].
So zip(*my_dict.items()) is [('a', 'b', 'c'), (1, 2, 3)].
And random.choices(('a', 'b', 'c'), (1, 2, 3)) is exactly what you want.