为了账号安全,请及时绑定邮箱和手机立即绑定

合并具有共同元素的列表

/ 猿问

合并具有共同元素的列表

倚天杖 2019-11-14 15:20:23

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


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


查看完整描述

3 回答

?
慕标琳琳

您可以将列表看作是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。


查看完整回答
反对 回复 2019-11-14
?
繁花如伊

算法:


从列表中取出第一组A

对于列表中的其他集合B,如果B具有与A共同的元素,则将B加入A;从列表中删除B

重复2。直到不再与A重叠

将A投入生产

重复1.与其余列表

因此,您可能想使用集合而不是列表。以下程序应执行此操作。


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


out = []

while len(l)>0:

    first, *rest = l

    first = set(first)


    lf = -1

    while len(first)>lf:

        lf = len(first)


        rest2 = []

        for r in rest:

            if len(first.intersection(set(r)))>0:

                first |= set(r)

            else:

                rest2.append(r)     

        rest = rest2


    out.append(first)

    l = rest


print(out)


查看完整回答
反对 回复 2019-11-14
?
蛊毒传说

我遇到了试图合并具有通用值的列表的同一问题。此示例可能是您要查找的。它仅循环遍历列表一次,并随即更新结果集。


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


查看完整回答
反对 回复 2019-11-14

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信