Python объединить несколько списков с пересечением

Question

Возможный дубликат:
Python: простое объединение списков на основе пересечений

У меня есть несколько списков:

 list=[[1,2,3],[3,5,6],[8,9,10],[11,12,13]]

Есть ли умный и быстрый способ получить все подсписки хотя бы с одним пересечением. В моем примере я хочу, чтобы код возвращался

 result=[[1,2,3,5,6],[8,9,10],[11,12,13]]

Answer 1

Это работает, но, возможно, не очень элегантно:

def merge_lists(l):
        s=map(set, l)
        i, n=0, len(s)
        while i < n-1:
                for j in xrange(i+1, n):
                        if s[i].intersection(s[j]):
                                s[i].update(s[j])
                                del s[j]
                                n-=1
                                break
                else:
                        i+=1
        return [sorted(i) for i in s]

Answer 2

Хороший вопрос! Намного проще, если вы думаете о ней как о проблеме связанных компонентов в графе. Следующий код использует отличный networkx библиотека графов и pairs Функция из этого вопроса.

def pairs(lst):
    i = iter(lst)
    first = prev = item = i.next()
    for item in i:
        yield prev, item
        prev = item
    yield item, first

lists = [[1,2,3],[3,5,6],[8,9,10],[11,12,13]]

import networkx
g = networkx.Graph()
for sub_list in lists:
    for edge in pairs(sub_list):
            g.add_edge(*edge)

networkx.connected_components(g)
[[1, 2, 3, 5, 6], [8, 9, 10], [11, 12, 13]]

---

объяснение

Создаем новый (пустой) график g, Для каждого подсписка в lists, рассмотреть его элементы как узлы графа и добавить ребро между ними. (Поскольку нас заботит только связность, нам не нужно добавлять все ребра - только соседние!) Обратите внимание, что add_edge берет два объекта, обрабатывает их как узлы (и добавляет их, если их там еще нет) и добавляет грань между ними.

Тогда мы просто находим связные компоненты графа - решенная проблема! - и вывести их как наши пересекающиеся множества.

Answer 3

Вы можете сделать это за один проход данных:

list_of_lists = [[1, 2, 3], [3, 5, 6], [8, 9, 10], [11, 12, 13]]
sets = {}
for lst in list_of_lists:
    s = set(lst)
    t = set()
    for x in s:
        if x in sets:
            t.update(sets[x])
        else:
            sets[x] = s
    for y in t:
        sets[y] = s
    s.update(t)
ids = set()
for s in sets.itervalues():
    if id(s) not in ids:
        ids.add(id(s))
        print s

Это создает словарь sets сопоставление каждого элемента с набором, к которому он принадлежит. Если какой-либо элемент был замечен ранее, его набор включается в текущий, и все дикторные записи, сопоставленные с предыдущим набором, обновляются.

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