列表中不同元组元素的组合

Question

我有一个包含元组的列表，比如说：[(1, 2, 3), (2, 4)]（这个列表的长度和元组的长度可能会变化），我想要得到所有组合，这些组合必须至少包含每个元组中的一个元素，但也可以包含更多的元素。

所以在这个例子中，结果应该是这样的：
[[1, 2, 3, 2, 4], [1, 2, 2, 4], [2, 3, 2, 4], [1, 2, 4], [2, 2, 4], [3, 2, 4], [1, 2, 3, 2], [1, 2, 3, 4], [1, 2, 2], [1, 2, 4], [2, 3, 2], [2, 3, 4], [1, 2], [1, 4], [2, 2], [2, 4], [3, 2], [3, 4]]

最小的结果应该包含的元素数量和原始列表中的元组数量相等，而最大的结果应该包含所有元组中的所有元素。

元素的顺序不重要，并且重复的元素最终应该被去掉（比如说[1, 2, 3, 2, 4] = [1, 2, 3, 4]，在结果中只出现一次，类似地[3, 2] = [2, 3]等等），我想在创建完整列表后再进行排序和去重。

那么，最好的方法是什么呢？老实说，我甚至不知道该怎么开始……

Answer 1

我们用 X 和 Y 来表示两个列表，它们的长度分别用 |X| 和 |Y| 来表示。

列表 X 的所有子集叫做 幂集(powerset)，它的长度是 2^|X|；而列表 Y 的幂集长度是 2^|Y|。

所以这两个幂集的乘积长度是 2^(|X|+|Y|)。对于这个乘积中的每一个项目，我们需要把各部分组合起来，然后取集合（这样可以去掉重复的部分），形成一个新的集合。接着，我们还需要对这个集合再取一次集合，以去掉重复的项目。这样做可能会占用很多内存，因为需要一次性把整个集合都放在内存里。

不过，我觉得有个更快的方法可以得到想要的结果。如果把 X 和 Y 合并成一个集合 XY，那么 XY 的幂集长度是 2^(|XY|)。如果 X 和 Y 有共同的项目，这个长度就会小于 2^(|X|+|Y|)。这样，每有一个共同的项目，你就能节省一半的工作量。

对于这个幂集中的每一个项目，我们只需要检查是否有来自 X 的元素和来自 Y 的元素。把所有这样的项目收集起来，就完成了。这要简单得多，而且占用的内存也少，因为结果可以通过迭代器生成。

---

import itertools as IT

def powerset(iterable, reverse=False, rvals=None):
    """powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"""
    s = list(iterable)
    N = len(s)
    if rvals is None:
        rvals = range(N, -1, -1) if reverse else range(N + 1)
    return IT.chain.from_iterable(
        IT.combinations(s, r) for r in rvals)

def powerreps(X, Y):
    """
    Return powerset with at least one representative from X and Y
    """
    XY = set(X).union(Y)
    for rep in powerset(XY, rvals=range(2, len(XY))):
        if any(x in rep for x in X) and any(y in rep for y in Y):
            yield rep

X, Y = (1, 2, 3), (2, 4)
print(list(powerreps(X, Y)))

产生

[(1, 2), (1, 4), (2, 3), (2, 4), (3, 4), (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (1, 2, 3, 4)]

Answer 2

你想要的是集合L中所有项的幂集的笛卡尔积，但如果其中有任何一个是空的，就不算。一个简单的方法就是在构建幂集的时候，把空的元素直接排除掉。

from itertools import product, combinations, chain
L = [(1, 2, 3), (2, 4)]
def powerset(iterable):
    "powerset minus the empty element"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(1, len(s)+1))

print [list(chain.from_iterable(c)) for c in product(*(powerset(x) for x in L))]

打印输出

[[1, 2], [1, 4], [1, 2, 4], [2, 2], [2, 4], [2, 2, 4], [3, 2], [3, 4], [3, 2, 4], [1, 2, 2], [1, 2, 4], [1, 2, 2, 4], [1, 3, 2], [1, 3, 4], [1, 3, 2, 4], [2, 3, 2], [2, 3, 4], [2, 3, 2, 4], [1, 2, 3, 2], [1, 2, 3, 4], [1, 2, 3, 2, 4]]