Объединение элементов в списке списка на основе наличия общих элементов

Question

У меня есть список списков, например,

list=[[a], [b], [c], [d],[e],[f], [a,f], [b,c], [c,e], [b, d,f]]

Обратите внимание, что он включает в себя одиночные и комбинации.

Что я хотел бы сделать, это перебрать список так, чтобы новый списоккаждой возможной комбинации этих подкомпонентов добавляется в список списков, если и только если они имеют хотя бы одну общую запись.

, поэтому продукт выглядит следующим образом:

list2=[[a], [b], [c], [d],[e],[f], [a,f], [b,c], [c,e], [b, d,f], **[b,c,e], [a,b,d,f], [b,c,d,f], [b,c,d,e,f], [a,b,c,d,e,f]]**

Примечаниеновая часть списка содержит исходный список списков

Answer 1

def similar(x):
    prev_l = 0
    while prev_l != len(x):
        to_add = []
        prev_l = len(x)
        for i in x:
            if len(i) == 1:
                continue
            for j in x:
                if len(j) == 1:
                    continue
                if any([_ in j for _ in i]) and not any([set(i+j) == set(_) for _ in x]) and not any([set(i+j) == set(_) for _ in to_add]) and i != j:
                    to_add.append(list(set(i+j)))
        x += to_add
    return x

Ввод:

>>> l = [['a'], ['b'], ['c'], ['d'],['e'],['f'], ['a','f'], ['b','c'], ['c','e'], ['b', 'd','f']]
>>> similar(l)

Ввод:

>>> l
[['a'], ['b'], ['c'], ['d'], ['e'], ['f'], ['a', 'f'], ['b', 'c'], ['c', 'e'], ['b', 'd', 'f'], ['b', 'a', 'd', 'f'], ['b', 'e', 'c'], ['b', 'd', 'c', 'f'], ['b', 'a', 'f', 'd', 'c'], ['b', 'f', 'e', 'd', 'c'], ['b', 'a', 'f', 'e', 'd', 'c']]

Следует отметить, что в худшем случае это O(n^3).Если вы используете это для чего-то, Флойд Уорсхолл, я бы не слишком волновался, так как в любом случае у него есть O(n^3), но если нет, то вам непременно следует заполнить матрицу расстояний, а затем искать в ней смежность.