python - 计算集合之间的乘积，仅保留不重复项的乘积

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