计算集合之间的乘积，只保留没有重复项的乘积

Question

我有一个类似于 [{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}] 的集合列表，我需要计算这些集合之间的乘积，但只保留 不重复数字的解决方案 .我找到了一个使用 itertools.product 的解决方案，但这仍然计算所有产品，我想知道是否有一个内置方法可以立即产生我想要的东西（或者如果你有一个操纵数据结构以加速计算时间的建议被广泛接受）。

我的解决方案：

from itertools import product

def pick(sets):
    for p in product(*sets):
        if len(set(p)) == len(p):
            yield p

这将导致所需的输出：

>>> x = [{i, i+1} for i in range(5)]
>>> for p in pick(x):
...     print(p)
...
(0, 1, 2, 3, 4)
(0, 1, 2, 3, 5)
(0, 1, 2, 4, 5)
(0, 1, 3, 4, 5)
(0, 2, 3, 4, 5)
(1, 2, 3, 4, 5)

Answer 1

def pick(sets, excluding=frozenset()):
    if not sets:
        yield ()
        return
    for x in sets[0] - excluding:
        for rest in pick(sets[1:], excluding | {x}):
            yield (x,) + rest

计算集合之间的乘积，只保留没有重复项的乘积

Calculate product between sets, keeping only products without repeated items

python

set

cartesian-product