Recipe4.21.Randomly Picking Items with Given Probabilities

Recipe 4.21. Randomly Picking Items with Given Probabilities

Credit: Kevin Parks, Peter Cogolo

Problem

You want to pick an item at random from a list, just about as random.choice does, but you need to pick the various items with different probabilities given in another list, rather than picking any item with equal probability as random.choice does.

Solution

Module random in the standard Python library offers a wealth of possibilities for generating and using pseudo-random numbers, but it does not offer this specific functionality, so we must code it as a function of our own:

import random def random_pick(some_list, probabilities):     x = random.uniform(0, 1)     cumulative_probability = 0.0     for item, item_probability in zip(some_list, probabilities):         cumulative_probability += item_probability         if x < cumulative_probability: break     return item

Discussion

Module random in the standard Python library does not have the weighted choice functionality that is sometimes needed in games, simulations, and random tests, so I wrote this recipe to supply this functionality. The recipe uses module random's function uniform to get a uniformly distributed pseudo-random number between 0.0 and 1.0, then loops in parallel on items and their probabilities, computing the increasing cumulative probability, until the latter becomes greater than the pseudo-random number.

The recipe assumes, but does not check, that probabilities is a sequence with just as many items as some_list, which are probabilitiesthat is, numbers between 0.0 and 1.0, summing up to 1.0; if these assumptions are violated, you may still get some random picks, but they will not follow the (inconsistent) specifications encoded in the function's arguments. You may want to add some assert statements at the start of the function to check that the arguments make sense, such as:

    assert len(some_list) == len(probabilities)     assert 0 <= min(probabilities) and max(probabilities) <= 1     assert abs(sum(probabilities)-1.0) < 1.0e-5

However, these checks can be quite time consuming, so I don't normally use them and have not included them in the official Solution.

As I already mentioned, the problem solved in this recipe requires items to be associated with probabilitiesnumbers between 0 and 1, summing up to 1. A related but slightly different task is to get random picks with weighted relative probabilities given by small non-negative integersodds, rather than probabilities. For this related problem, the best solution is a generator, with an internal structure that is rather different from the function random_pick given in this recipe's Solution:

import random def random_picks(sequence, relative_odds):     table = [ z for x, y in zip(sequence, relative_odds) for z in [x]*y ]     while True:         yield random.choice(table)

This generator works by first preparing a table whose total number of items is sum(relative_odds), each item of seq appearing in the table as many times as the small non-negative integer that is its corresponding item in relative_odds. Once the table is prepared, the generator's body is tiny and fast, as it simply delegates to random.choice the picking of each random item it yields. Typical uses of this random_picks generator might be:

>>> x = random_picks('ciao', [1, 1, 3, 2]) >>> for two_chars in zip('boo', x): print ''.join(two_chars), bc oa oa >>> import itertools >>> print ''.join(itertools.islice(x, 8)) icacaoco

Recipe4.21.Randomly Picking Items with Given Probabilities