列表操作以汇总和缩小带有子列表的列表

Question

我有一个基本如下所示的列表：

[[A, B], [A, C], [D,E]]

其中 A、B、C、D 和 E 是电路的节点。当两个节点一起在一个列表中时，它们处于相同的电位，所以在我的情况下，A 和 B，A 和 C，最后还有 D 和 E 基本相等。

因为A和B，而且A和C相等，所以B和C也应该相等。

我想做的是：我需要创建一个基本如下所示的列表：

[[A, B, C], [D,E]]

所以它应该将所有基本相等的节点汇总到一个列表中，并将每个相等节点的列表放入一个最终列表，如上面的列表。我正在考虑使用集合，例如使用交集和联合，但我还没有想出来。

也许有人可以提供帮助并提前致谢！

[编辑] 这是我目前的尝试：

wireEnds = self.wireEnds.copy()
for currentNodePair in wireEnds:
    foundInSubSet = False
    print("currentNodePair:",currentNodePair)
    for subSet in self.commonNodes:
        print("subSet:",subSet)
        if (currentNodePair[0] in subSet) or (currentNodePair[1] in subSet): 
            subSet.add(currentNodePair[0])
            subSet.add(currentNodePair[1])
            print("Adding to subset:",currentNodePair)
            foundInSubSet = True
            continue
    if not foundInSubSet:
        print("Not found, creating new subSet:",currentNodePair)
         self.commonNodes.append({currentNodePair[0], currentNodePair[1]})

请注意，我使用集合而不是子列表，因为我不想在我的子列表中重复。

Answer 1

由于您拥有的是一个图并且您想要查找 connected components，您可以使用具有联合查找数据结构实现的 Networkx：

from networkx.utils.union_find import UnionFind
sets = UnionFind()
for gp in lst:
    sets.union(*gp)
out = [list(s) for s in sets.to_sets()]


[['A', 'B', 'C'], ['E', 'D']]

Answer 2

好的，谢谢@enke，这比我的解决方案简单得多，但也许你可以看看！

def version_3(list_in):
  output = [set(list_in[0])]
  for sublist in list_in[1:]:
    current_set = set(sublist)
    found_in = []
    for group in output:
      current_group = set(group)
      if current_set.intersection(current_group):
        found_in.append(current_group)
    
    if found_in:
      for group in found_in:
        output.remove(group)
        current_set = current_set.union(group)
      output.append(current_set)
    else:
      output.append(set(sublist))
      
  return output

列表操作以汇总和缩小带有子列表的列表

List operation to summarize and shrink down list with sublists

python

list

set