从组合中随机选择

Question

我可以列出所有使用的组合,list(itertools.combinations(range(n), m)) 但这通常会非常大.

给定n和m,如何在不首先构建大量列表的情况下随机均匀地选择组合？

Answer 1

在itertools模块中有一个从迭代中返回随机组合的方法.下面是代码的两个版本,一个用于Python 2.x,另一个用于Python 3.x - 在这两种情况下,您使用的是生成器,这意味着您不在内存中创建大型迭代.

假设Python 2.x

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)

在你的情况下,这样做很简单:

>>> import random
>>> 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)
>>> n = 10
>>> m = 3
>>> print(random_combination(range(n), m))
(3, 5, 9) # Returns a random tuple with length 3 from the iterable range(10)

在Python 3.x的情况下

在Python 3.x的情况下,您替换xrange调用,range但用例仍然是相同的.

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

Answer 2

来自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)