python - 从组合中随机选择

Question

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

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

Answer 1

在itertools模块有一个从 iterable 返回随机组合的方法。下面是代码的两个版本，一个用于 Python 2.x，一个用于 Python 3.x - 在这两种情况下，您都使用 generator这意味着您不会在内存中创建一个大的可迭代对象。

假定 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)