来自 itertools 的随机链

Question

我正在从python docs复制一个示例。

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

我们如何随机化我们得到的值的顺序，而powerset仍然懒惰地评估结果？

编辑：我想要它的原因是我想计算派生集的总和，并在找到两个具有相同总和的集合时立即停止。如果我没记错的话，问题是 NP-complete。

Answer 1

itertools.combinations()按照输入的设定顺序为我们提供结果。鉴于此，我们可以打乱输入列表以生成随机顺序的元素（显然，结果的可能顺序会少得多）。

def random_powerset(iterable):
     s = list(iterable)
     lengths = list(range(len(s)+1))
     shuffle(lengths)
     return chain.from_iterable(combinations(s, r) for r in lengths if not shuffle(s))

（这是一个有点丑陋的黑客 - 我们知道shuffle(s)总是会返回False，因此我们可以将其添加为条件以确保它在每次调用时运行combinations()。）

我们预先生成长度列表，以便我们也可以对其进行洗牌。

它不是完全随机的（仍然会有一个顺序 - 例如，长度为 n 的所有元素都会聚集在一起，并且这些元素将按照输入的随机顺序排列），但会有相当多的数量随机性，如果这对你来说足够了。

输出示例：

>>> list(random_powerset(range(3)))
[(), (2,), (0,), (1,), (2, 1), (2, 0), (1, 0), (1, 2, 0)]
>>> list(random_powerset(range(3)))
[(), (0, 1), (0, 2), (1, 2), (0, 1, 2), (2,), (0,), (1,)]
>>> list(random_powerset(range(3)))
[(0, 1, 2), (2,), (1,), (0,), (0, 2), (0, 1), (2, 1), ()]
>>> list(random_powerset(range(3)))
[(1, 2, 0), (0,), (2,), (1,), (), (0, 1), (0, 2), (1, 2)]
>>> list(random_powerset(range(3)))
[(), (2, 1), (2, 0), (1, 0), (0,), (2,), (1,), (2, 1, 0)]
>>> list(random_powerset(range(3)))
[(1, 0), (1, 2), (0, 2), (0, 2, 1), (), (1,), (0,), (2,)]

我认为这是你在不让它变得不懒惰的情况下能做的最好的事情。