如果python中至少有一个值匹配，则联合列表

Let's say I have a list of lists, for example:

假设我有一个列表，例如:

[[0, 2], [0, 1], [2, 3], [4, 5, 7, 8], [6, 4]]

and if at least one of the values on a list is the same that another one of a different list, i would like to unite the lists so in the example the final result would be:

如果一个列表中的至少一个值与另一个不同的列表中的一个值相同，我想将这些列表合并起来，在这个例子中，最终的结果是:

[[0, 1, 2, 3], [4, 5, 6, 7, 8]]

I really don't care about the order of the values inside the list [0, 1, 2, 3] or [0, 2, 1, 3].

我真的不关心list里面的值的顺序[0,1,2,3]或者[0,2,1,3]。

I tried to do it but it doesn't work. So have you got any ideas? Thanks.

我试着去做，但没有用。你有什么想法吗?谢谢。

Edit(sorry for not posting the code that i tried before): What i tried to do was the following:

编辑(不好意思没有发布我之前尝试过的代码):我尝试做的是:

for p in llista:
        for q in p:
            for k in llista:
                if p==k:
                    llista.remove(k)
                else:
                    for h in k:
                        if p!=k:
                            if q==h:
                                k.remove(h)
                                for t in k:
                                    if t not in p:
                                        p.append(t)
    llista_final = [x for x in llista if x != []]

Where llista is the list of lists.

其中llista是列表的列表。

3 个解决方案

#1

I have to admit this is a tricky problem. I'm really curious what does this problem represent and/or where did you find it out...

我得承认这是个棘手的问题。我很好奇这个问题代表什么，或者你在哪里发现的…

I initially have thought this is just a graph connected components problem, but I wanted to take a shortcut from creating an explicit representation of the graph, running bfs, etc...

我最初认为这只是一个图连接组件的问题，但我想从创建图的显式表示、运行bfs等方面采取捷径……

The idea of the solution is this: for every sublist, check if it has some common element with any other sublist, and replace that with their union.

解决方案的思想是:对于每个子列表，检查它是否有与其他子列表相同的元素，并将其替换为它们的联合。

Not very pythonic, but here it is:

不是很毕达哥拉斯式的，但它是这样的:

def merge(l):
    l = list(map(tuple, l))
    for i, h in enumerate(l):
        sh = set(h)
        for j, k in enumerate(l):
            if i == j: continue
            sk = set(k)
            if sh & sk: # h and k have some element in common
                l[j] = tuple(sh | sk)
    return list(map(list, set(l)))

#2

Here is a function that does what you want. I tried to use self-documenting variable names and comments to help you understand how this code works. As far as I can tell, the code is pythonic. I used sets to speed up and simplify some of the operations. The downside of that is that the items in your input list-of-lists must be hashable, but your example uses integers which works perfectly well.

这是一个函数。我尝试使用自文档化的变量名和注释来帮助您理解这段代码是如何工作的。就我所知，代码是python的。我使用集合来加速和简化一些操作。缺点是，输入列表中的条目必须是可清洗的，但是您的示例使用的是整数。

def cliquesfromlistoflists(inputlistoflists):
    """Given a list of lists, return a new list of lists that unites
    the old lists that have at least one element in common.
    """
    listofdisjointsets = []
    for inputlist in inputlistoflists:
        # Update the list of disjoint sets using the current sublist
        inputset = set(inputlist)
        unionofsetsoverlappinginputset = inputset.copy()
        listofdisjointsetsnotoverlappinginputset = []
        for aset in listofdisjointsets:
            # Unite set if overlaps the new input set, else just store it
            if aset.isdisjoint(inputset):
                listofdisjointsetsnotoverlappinginputset.append(aset)
            else:
                unionofsetsoverlappinginputset.update(aset)
        listofdisjointsets = (listofdisjointsetsnotoverlappinginputset 
                              + [unionofsetsoverlappinginputset])
    # Return the information in a list-of-lists format
    return [list(aset) for aset in listofdisjointsets]

print(cliquesfromlistoflists([[0, 2], [0, 1], [2, 3], [4, 5, 7, 8], [6, 4]]))
# printout is [[0, 1, 2, 3], [4, 5, 6, 7, 8]]

#3

-1

This solution modifies the generic breadth-first search to gradually diminish the initial deque and update a result list with either a combination should a match be found or a list addition if no grouping is discovered:

该解决方案修改了一般的广度优先搜索，以逐渐减少初始deque，并在发现匹配或未发现分组时使用组合更新结果列表:

from collections import deque
d = deque([[0,2] , [0,1] , [2,3] , [4,5,7,8] , [6,4]])
result = [d.popleft()]
while d:
  v = d.popleft()
  result = [list(set(i+v)) if any(c in i for c in v) else i for i in result] if any(any(c in i for c in v) for i in result) else result + [v]

Output:

输出:

[[0, 1, 2, 3], [8, 4, 5, 6, 7]]

#1