我想基于相似的属性对元组进行分组

Question

我有一个元组列表。[（1、2），（2、3），（4、3），（5、6），（6、7），（8、2）]

我想根据连接的元组将它们分组为列表（具有相关值）。

因此最终结果是两个相关元组值的列表= [[1、2、3、4、8]，[5、6、7]]

如何编写一个函数来做到这一点？这是工作面试的问题。我试图在Python中执行此操作，但是我很沮丧，只是想看看答案背后的逻辑，所以即使是伪代码也可以帮助我，所以我可以看看我做错了什么。

我当时只有几分钟的时间来做，但是这是我尝试过的：

def find_partitions(connections):
 theBigList = []     # List of Lists
 list1 = []          # The initial list to store lists
 theBigList.append(list1)

 for list in theBigList:
 list.append(connection[1[0], 1[1]])
     for i in connections:
         if i[0] in list or i[1] in list:
             list.append(i[0], i[1])

         else:
             newList = []
             theBigList.append(newList)

本质上，这家伙想要一个相关值的列表。我尝试使用for循环，但是意识到它不起作用，然后时间用完了。

Answer 1

在填写组件时，在每个阶段都需要考虑三种情况（因为您 必须 匹配重叠的组）：

1. x或y都没有在已找到的任何组件中。
2. 两者已经在 不同的集合中 ，x在set_i中，y在set_j中。
3. 一个或两个都在一个组件中，x在set_i中或y在set_i中。

我们可以使用内置的set帮助。 （请参阅@jwpat和@DSM的更复杂的示例） ：

def connected_components(lst):
    components = [] # list of sets
    for (x,y) in lst:
        i = j = set_i = set_j = None
        for k, c in enumerate(components):
            if x in c:
                i, set_i = k, c
            if y in c:
                j, set_j = k, c

        #case1 (or already in same set)
        if i == j:
             if i == None:
                 components.append(set([x,y]))
             continue

        #case2
        if i != None and j != None:
            components = [components[k] for k in range(len(components)) if k!=i and k!=j]
            components.append(set_i | set_j)
            continue

        #case3
        if j != None:
            components[j].add(x)
        if i != None:
            components[i].add(y)

    return components

lst = [(1, 2), (2, 3), (4, 3), (5, 6), (6, 7), (8, 2)]
connected_components(lst)
# [set([8, 1, 2, 3, 4]), set([5, 6, 7])]
map(list, connected_components(lst))
# [[8, 1, 2, 3, 4], [5, 6, 7]]

connected_components([(1, 2), (4, 3), (2, 3), (5, 6), (6, 7), (8, 2)])
# [set([8, 1, 2, 3, 4]), set([5, 6, 7])] # @jwpat's example

connected_components([[1, 3], [2, 4], [3, 4]]
# [set([1, 2, 3, 4])] # @DSM's example

这当然不是最有效的方法，但是可能与他们期望的方法类似。 正如乔恩·克莱门茨（Jon Clements）所指出的那样，有一个用于这些类型的计算的库：
networkx
，在该库中它们会更加高效。