python - 在列表列表中查找重叠列表

Question

我有一个列表列表，需要根据常见的列表项进行合并。共享元素的列表需要合并在一起以形成集群。

我考虑过广度优先遍历来做这个，但是因为list of list的排列方式，很难实现遍历

列表示例:

input: 
[
 [1,2,3],
 [2,4,5],
 [4,6,8],
 [9,10,16],
 [16,18,19],
 [20,21,22]
]

output: [[1,2,3,4,5,6,8], [9,10,16,18,19], [20,21,22]]

前三个列表需要合并为一个列表(第一个列表和第二个列表有2个，第二个和第三个列表共享4个)，第四个和第五个需要合并，因为两者共享16个。第三个是不与任何其他列表合并，因为它不与其他列表共享任何元素。

虽然这可以在 O(n^2) 时间内完成(n 是列表的数量)，但我正在尝试找到最有效的方法。

Answer 1

您可以在 O(N * log N) 中执行此操作，其中 N 是所有列表中的项目总数。

使用 Union Find 数据结构的想法很简单:

1. 首先让我们为输入中的每个唯一项目创建 N 个不相交的集合
2. 为每个列表的所有相邻项目合并不相交的集合
3. 从不相交的集合中收集结果

示例代码:

def Find(id,P):
    if P[id]<0 : return id
    P[id]=Find(P[id],P)
    return P[id]

def Union(id1, id2, p):
    id1 = Find(id1,P)
    id2 = Find(id2,P)
    if id1 != id2:
        P[id2]=id1

input=[
 [1,2,3],
 [2,4,5],
 [4,6,8],
 [9,10,16],
 [16,18,19],
 [20,21,22]
]

P = {}

for list in input :
    for item in list :
        P[item] = -1

for list in input :
    for i in range(1,len(list)):
            Union(list[i-1], list[i], P)

ans = {}
for list in input :
    for item in list :
        if Find(item,P) not in ans:
            ans[Find(item,P)] = []
        ans[Find(item,P)].append(item)

ans = [set(x) for x in ans.values()]
print(ans)