使用Python在更大的列表中查找兼容的列表

Question

大家好，谢谢你们阅读我的问题。你知道吗

所以基本上我有一个列表或集合，包含从0到n的值

列表的一个例子是n=4。你知道吗

L1 = [0, 1, 3, 4]

我有一个更大的清单，里面有他们。例如：

L = [L1, L2, L3, ..., Lm]

我想做的是创建一个列表，列出所有可能的兼容子集，它们之间没有交集。你知道吗

例如，如果我有：

L1 = [0, 1, 2] and L2 = [3, 4, 5, 6, 7]

这两个被认为是兼容的，因为它们的交集是空的。你知道吗

我已经编写了这个函数，它获取这些列表的列表，并检查它们是否相互兼容。你知道吗

def areListsCompatible(list):
     o = set(list[0])
     for i in range(1, len(list)):
         o = o & set(list[i])
         if(bool(o)==True):
             return False
return True

现在我的问题是如何编写一个函数，它接受一个列表，并找到所有可能的兼容列表组合，2个列表可以兼容，3个甚至4个？你知道吗

我正在考虑递归，但似乎无法正确完成。你知道吗

有什么帮助吗？非常感谢。你知道吗

编辑：

有人让我把一个样本输入和输出。你知道吗

输入：

L = [[0, 1, 2], [3, 4, 5], [0, 1], [2, 3], [6, 7]]

输出：

O = [[[0, 1, 2], [3, 4, 5], [6, 7]], #O1
     [[0, 1], [3, 4, 5], [6, 7]],    #O2
     [[0, 1], [2, 3], [6, 7]],       #O3
     ...
    ]

等等。。。你知道吗

Answer 1

下面的递归生成器函数应该可以工作。我相信性能可以提高。你知道吗

def subsets(lsts):
    if not lsts:
        return
    for i, lst in enumerate(lsts):
        yield [lst]
        s = set(lst)
        pool = [x for x in lsts[i+1:] if not s.intersection(x)]
        for subs in subsets(pool):
            yield [lst] + subs

>>> L = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]]
>>> list(subsets(L))
[[[0, 1]], 
 [[0, 1], [2, 3]], 
 [[0, 1], [2, 3], [4, 5]], 
 [[0, 1], [3, 4]], 
 [[0, 1], [4, 5]], 
 [[1, 2]], 
 [[1, 2], [3, 4]], 
 [[1, 2], [4, 5]], 
 [[2, 3]], 
 [[2, 3], [4, 5]], 
 [[3, 4]], 
 [[4, 5]]]

如果您只需要完全详尽的子集列表（不能添加其他子集），则可以进行一些小的调整：

def subsets(lsts, make_unique=True, used=None):
    if not lsts:
        yield []
    used = set(used or [])
    if make_unique:
        lsts = sorted(map(list, set(map(tuple, lsts))))
    for i, lst in enumerate(lsts):
        s = set(lst)
        pool = [x for x in lsts if not s.intersection(x)]
        for subs in subsets(pool, make_unique=False, used=used):
            if not used.intersection(map(tuple, subs)):
                yield [lst] + subs
            used.add(tuple(lst))

>>> list(subsets(L))
[[[0, 1], [2, 3], [4, 5]], 
 [[0, 1], [3, 4]], 
 [[1, 2], [3, 4]], 
 [[1, 2], [4, 5]]]
>>> L = [[0, 1, 2], [3, 4, 5], [0, 1], [2, 3], [6, 7]]
>>> list(subsets(L))
[[[0, 1], [2, 3], [6, 7]], 
 [[0, 1], [3, 4, 5], [6, 7]], 
 [[0, 1, 2], [3, 4, 5], [6, 7]]]