Choose at random from combinations

I can make a list of all combinations using list(itertools.combinations(range(n), m)) but this will typically be very large.

Given n and m, how can I choose a combination uniformly at random without first constructing a massive list??

Answer

From http://docs.python.org/2/library/itertools.html#recipes

def random_combination(iterable, r):
    "Random selection from itertools.combinations(iterable, r)"
    pool = tuple(iterable)
    n = len(pool)
    indices = sorted(random.sample(xrange(n), r))
    return tuple(pool[i] for i in indices)