在Python中从列表元素中查找互斥集合的组合

在我目前正在进行的一个项目中，我已经实现了大约 80% 我希望我的程序完成的任务，我对结果非常满意。

在剩下的 20% 中，我面临着一个让我有点困惑的问题，不知道如何解决。 这里是：

我想出了一个包含多个数字（任意长度）的列表列表 例如：

listElement[0] = [1, 2, 3]
listElement[1] = [3, 6, 8]
listElement[2] = [4, 9]
listElement[4] = [6, 11]
listElement[n] = [x, y, z...]

其中n可以达到40,000左右。

假设每个列表元素是一组数字（在数学意义上），我想做的是导出互斥集合的所有组合；也就是说，类似于上述列表元素的幂集，但排除所有非不相交集元素。

因此，为了继续 n=4 的示例，我想提出一个包含以下组合的列表：

newlistElement[0] = [1, 2, 3]
newlistElement[1] = [3, 6, 8]
newlistElement[2] = [4, 9]
newlistElement[4] = [6, 11] 
newlistElement[5] = [[1, 2, 3], [4, 9]]
newlistElement[6] = [[1, 2, 3], [6, 11]]
newlistElement[7] = [[1, 2, 3], [4, 9], [6, 11]]
newlistElement[8] = [[3, 6, 8], [4, 9]]
newlistElement[9] = [[4, 9], [6, 11]

例如，无效的情况是组合 [[1, 2, 3], [3, 6, 8]]，因为 3 在两个元素中很常见。 有什么优雅的方法可以做到这一点吗？如果有任何反馈，我将非常感激。

我还必须指定我不想执行 powerset 函数，因为初始列表可能有相当多的元素（正如我所说，n 可能高达 40000），并且采用具有如此多元素的 powerset 永远不会完成。

我会使用发电机：

import itertools

def comb(seq):
   for n in range(1, len(seq)):
      for c in itertools.combinations(seq, n): # all combinations of length n
         if len(set.union(*map(set, c))) == sum(len(s) for s in c): # pairwise disjoint?
            yield list(c)

for c in comb([[1, 2, 3], [3, 6, 8], [4, 9], [6, 11]]):
   print c

这会产生：

[[1, 2, 3]]
[[3, 6, 8]]
[[4, 9]]
[[6, 11]]
[[1, 2, 3], [4, 9]]
[[1, 2, 3], [6, 11]]
[[3, 6, 8], [4, 9]]
[[4, 9], [6, 11]]
[[1, 2, 3], [4, 9], [6, 11]]

如果您需要将结果存储在单个列表中：

print list(comb([[1, 2, 3], [3, 6, 8], [4, 9], [6, 11]]))