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

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

这应该可以解决问题：

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


grp1 = []
grp2 = []

for i in range(len(my_list)):
    j = i+1
    if my_list[i] not in grp1:
        for ele in my_list[i]:
            try:
                if ele in my_list[j]:
                    grp1.append(my_list[i])
                    grp1.append(my_list[j])
            except:
                pass
    else:
        continue

for lst in my_list:
    if lst not in grp1:
        grp2.append(lst)
    else:
        continue

print(grp1)
print(grp2)

Answer 2

类似于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，并且寻找 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]]]

Answer 3

这应该可以解决：

my_list = [[1, 2, 3, 4], [4, 5, 6, 7], [9, 10, 11, 12], [22, 17, 16, 15], [9, 88, 39, 58]]

group1 = []
group2 = []

def contains(list1, list2):
    for item in list1:
        if item in list2:
            return True
    return False

counter = 0
while counter < len(my_list):
    actualinnerlist = my_list[counter]
    actualmy_list = my_list[:counter] + my_list[counter+1:]
    print(f"\nactualinnerlist item: {actualinnerlist}")
    print(f"actualmy_list item: {actualmy_list}")

    for innerlist in actualmy_list:
        print(f"Actual Inner List: {actualmy_list}")
        print(f"Inner List: {innerlist}")
        if contains(actualinnerlist, innerlist):
            group1.append(actualinnerlist)
            counter += 1
            break
    else:
        group2.append(actualinnerlist)
        counter += 1

print (f"Group1: {group1}")
print (f"Group2: {group2}")

它只是比较列表，但在 while 循环中对列表进行切片以不与相同的元素进行比较。

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

Separate nested list into groups with disjoint elements

python

graph-theory

list

set

networkx