Как рекурсивно объединить подмножества в список в Python?

Можно взять два комплекта и уменьшить его:

def get_union(sets):
    def _rec(S, B):
        A = set(S)
        i = 0
        while i < len(B):
            if A.intersection(B[i]):
                A.update(B.pop(i))
                A, B = _rec(A, B)
            else:
                i += 1
        return A, B

    res = []
    while sets:
        C, sets = _rec(sets[0], sets[1:])
        res.append(list(C))
    return res


print(get_union([[1, 2, 3], [1, 5], [4, 5, 6], [7, 8]]))

Принты

[[1, 2, 3, 4, 5, 6], [8, 7]]

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

# Implementation of Union-Find (Disjoint Set)
class Node:
    def __init__(self):
        self.parent = self
        self.rank = 0

    def find(self):
        if self.parent.parent != self.parent:
            self.parent = self.parent.find()
        return self.parent

    def union(self, other):
        node = self.find()
        other = other.find()
        if node == other:
            return # was already in same set
        if node.rank > other.rank:
            node, other = other, node
        node.parent = other
        other.rank = max(other.rank, node.rank + 1)

from collections import defaultdict

def merge(sets):
    nodes = defaultdict(Node)
    for first, *rest in sets:
        for item in rest:
            nodes[item].union(nodes[first])
    merged = defaultdict(list)
    for item, node in nodes.items():
        merged[node.find()].append(item)
    return list(merged.values())

print(merge([[1, 2, 3], [1, 5], [4, 5, 6], [7, 8]]))

Я бы предложил использовать один collections.Counter для отслеживания элементов, которые появляются более чем в одном наборе, а затем использовать его для сортировки наборов на перекрывающиеся и непересекающиеся. Вот быстрая демонстрация:

from collections import Counter

my_sets = [{1, 2, 3}, {1, 5}, {4, 5, 6}, {7, 8}]

counts = Counter(i for s in my_sets for i in s)
merged_set = set()
remainder = []
for s in my_sets:
    if any(counts[i] > 1 for i in s):
        merged_set |= s
    else:
        remainder.append(s)

дает нам:

>>> [merged_set] + remainder
[{1, 2, 3, 4, 5, 6}, {8, 7}]

Обратите внимание, что это зависит от того, является ли my_sets набором наборов, а не списками, как в вашем исходном вопросе. Если это набор произвольных списков, измените Counter так, чтобы он учитывал только один элемент в каждом подсписке, превратив его в набор перед подсчетом:

counts = Counter(i for s in my_sets for i in set(s))