我有一个元组列表。[（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循环，但是意识到它不起作用，然后时间用完了。
在填写组件时，在每个阶段都需要考虑三种情况（因为您 必须 匹配重叠的组）：
我们可以使用内置的set帮助。 （请参阅@jwpat和@DSM的更复杂的示例） ：
set
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，在该库中它们会更加高效。
