python - 将嵌套列表分成具有不相交元素的组

Question

我有一个看起来像这样的列表列表

my_list = [[1, 2, 3, 4], [4, 5, 6, 7], [9, 10, 11, 12]]

我想找到将列表分成两组的最佳方法，以便每组中的各个元素不重叠。例如，在上面的示例中，两组将是

group1 = [[1, 2, 3, 4], [4, 5, 6, 7]]
group2 = [[9, 10, 11, 12]]

这是因为 9、10、11、12 从未出现在 group1 的任何项目中。

Answer 1

类似于Combine lists with common elements , 解决这个问题的一种方法是从嵌套列表中定义一个图，将每个子列表视为 path ， 和 寻找 connected components :

import networkx as nx

my_list = [[1, 2, 3, 4], [4, 5, 6, 7], [9, 10, 11, 12]]

G=nx.Graph()
for l in my_list:
    nx.add_path(G, l)
components = list(nx.connected_components(G))
# [{1, 2, 3, 4, 5, 6, 7}, {9, 10, 11, 12}]    

groups = []
for component in components:
    group = []
    for path in my_list:
        if component.issuperset(path):
            group.append(path)
    groups.append(group)

---

groups
# [[[1, 2, 3, 4], [4, 5, 6, 7]], [[9, 10, 11, 12]]]