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< /code> 函数来自这个问题。

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的值中找到所有唯一的集合。请注意，虽然我将其实现为集合字典，但该代码也适用于列表而不是集合。