合并具有共同元素的列表

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_components

def 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 G

def 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']]