Найти совместимые списки в большем списке с 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]

Считается, что эти два объекта совместимы, поскольку их пересечение равно нулю.

Я уже написал эту функцию, которая берет список таких списков и проверяет, являются ли они all совместимы между собой.

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]]]