合并具有共同元素的列表

Question

我的输入是列表列表。其中一些共享共同的元素，例如。

L = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]

我需要合并所有共享一个公共元素的列表，并在没有更多具有相同项目的列表时重复此过程。我曾考虑过要使用布尔运算和while循环，但无法提出一个好的解决方案。

最终结果应为：

L = [['a','b','c','d','e','f','g','o','p'],['k']] 

Answer 1

您可以将列表看作是Graph的一种表示法，即['a','b','c']是一个3个节点相互连接的图形。您要解决的问题是在此图中找到连接的组件。您可以为此使用NetworkX，它的优点是可以保证正确无误：l = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]import networkx from networkx.algorithms.components.connected import connected_componentsdef to_graph(l):    G = networkx.Graph()    for part in l:        # each sublist is a bunch of nodes        G.add_nodes_from(part)        # it also imlies a number of edges:        G.add_edges_from(to_edges(part))    return Gdef to_edges(l):    """         treat `l` as a Graph and returns it's edges         to_edges(['a','b','c','d']) -> [(a,b), (b,c),(c,d)]    """    it = iter(l)    last = next(it)    for current in it:        yield last, current        last = current    G = to_graph(l)print connected_components(G)# prints [['a', 'c', 'b', 'e', 'd', 'g', 'f', 'o', 'p'], ['k']]为了自己有效地解决这个问题，无论如何，您都必须将列表转换为类似图形的内容，因此您最好从一开始就使用networkX。

Answer 2

我遇到了试图合并具有通用值的列表的同一问题。此示例可能是您要查找的。它仅循环遍历列表一次，并随即更新结果集。lists = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]lists = sorted([sorted(x) for x in lists]) #Sorts lists in place so you dont miss things. Trust me, needs to be done.resultslist = [] #Create the empty result list.if len(lists) >= 1: # If your list is empty then you dont need to do anything.    resultlist = [lists[0]] #Add the first item to your resultset    if len(lists) > 1: #If there is only one list in your list then you dont need to do anything.        for l in lists[1:]: #Loop through lists starting at list 1            listset = set(l) #Turn you list into a set            merged = False #Trigger            for index in range(len(resultlist)): #Use indexes of the list for speed.                rset = set(resultlist[index]) #Get list from you resultset as a set                if len(listset & rset) != 0: #If listset and rset have a common value then the len will be greater than 1                    resultlist[index] = list(listset | rset) #Update the resultlist with the updated union of listset and rset                    merged = True #Turn trigger to True                    break #Because you found a match there is no need to continue the for loop.            if not merged: #If there was no match then add the list to the resultset, so it doesnt get left out.                resultlist.append(l)print resultlist＃resultset = [['a', 'b', 'c', 'd', 'e', 'g', 'f', 'o', 'p'], ['k']]