用不相交的元素将嵌套列表分成几组 [英] Separate nested list into groups with disjoint elements

问题描述

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

I have list of list that looks like this

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

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

and I would like to find what's the best way to split the list into two groups so that the individual elements in each group are not overlapping. For instance, in the example above the two groups would be

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

这是因为9，10，11，12永远不会出现在group1的任何项目中.

and this is because 9, 10, 11, 12 never appear in any of the items of group1.

推荐答案

类似于合并具有常见元素的列表，解决此问题的方法可能是从嵌套列表中定义一个图形，将每个子列表作为路径，以及 寻找已连接的组件:

Similarly to Combine lists with common elements, a way to go about this could be to define a graph from the nested list, taking each sublist as a path, and looking for the 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]]]

这篇关于用不相交的元素将嵌套列表分成几组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！