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

Question

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

我考虑过广度优先遍历来做这件事，但是由于列表列表的排列方式，很难实现遍历

列表示例列表：

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 是列表的数量），但我试图找到最有效的方法。

标签： pythonalgorithmcomputer-sciencegraph-algorithm

Answer 1

您的内部列表没有重复的元素。如果这是一般情况，那么 Rosetta Code 上的集合合并任务有一个可以工作的 Python 解决方案。