unite列出python中是否至少有一个值匹配

Question

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

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

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

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

我真的不关心列表[0, 1, 2, 3]或[0, 2, 1, 3]中值的顺序。你知道吗

我试过了，但没用。你有什么想法吗？谢谢。你知道吗

编辑（很抱歉没有发布我以前尝试过的代码）： 我想做的是：

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 != []]

其中llista是列表列表。你知道吗

Answer 1

我得承认这是个棘手的问题。我真的很好奇这个问题代表什么和/或你在哪里发现的。。。你知道吗

我最初以为这只是一个图连接组件问题，但我想从创建图的显式表示、运行bfs等方面走捷径。。。你知道吗

解决方案的思想是：对于每个子列表，检查它是否与任何其他子列表有公共元素，并用它们的并集替换。你知道吗

不是很像Python，但这里是：

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)))

Answer 2

此解决方案修改了通用的广度优先搜索，以逐渐减少初始deque，并在找到匹配项时使用组合更新result列表，如果没有发现分组，则使用列表添加：

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]

输出：

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

Answer 3

这里有一个函数，它可以满足您的需要。我尝试使用自文档化变量名和注释来帮助您理解代码的工作原理。据我所知，代码是pythonic。我用集合来加速和简化一些操作。这样做的缺点是，列表的输入列表中的项必须是可散列的，但是您的示例使用的整数工作得非常好。你知道吗

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