查找元組列表中的重複項Python

Question

我想從下面給出的列表中找到匹配項。我的列表可能超大。

在元組「N1_10」的第一個項目在另一陣列中的利斯塔('N1_10', 'N3_98')

ListA = [[('N1_10', 'N2_28'), ('N1_35', 'N2_44')], 
      [('N1_22', 'N3_72'), ('N1_10', 'N3_98')], 
      [('N2_33', 'N3_28'), ('N2_55', 'N3_62'), ('N2_61', 'N3_37')]] 

複製和匹配與另一項目在第一陣列

元組在利斯塔('N1_10', 'N2_28')
元組在第二陣列

我想要的輸出是

輸出 - >[('N1_10','N2_28','N3_98') , ....，其餘任何比賽之一210鍵將進入相同的元組]

如果你們認爲，更改ListA的數據結構是更好的選擇，請隨時提供建議！ 感謝您的幫助！

簡化版本

列表A = [[（A，X），（B，K），（C，L），（d，米）]，[（E，d），（A，p），（G，S）]，[...] [...] ...]

wantedOutput - > [（一個，X，p （），（b，k），（c，l），（d，m，e），（g，s）.....]

Answer 1

更新：重讀您的問題後，您似乎嘗試創建等價類，而不是收集鍵的值。如果

[[(1, 2), (3, 4), (2, 3)]] 

應該成爲

[(1, 2, 3, 4)] 

，那麼你將需要解釋你的輸入爲曲線圖應用連接的組件算法。您可以將您的數據結構轉換爲adjacency list表示形式，並使用廣度優先或深度優先搜索遍歷它，或遍歷列表並構建disjoint sets。無論哪種情況，您的代碼都會突然涉及很多與圖形相關的複雜性，並且很難根據輸入的順序提供任何輸出排序保證。以下是基於廣度優先搜索的算法：

import collections 

# build an adjacency list representation of your input 
graph = collections.defaultdict(set) 
for l in ListA: 
    for first, second in l: 
     graph[first].add(second) 
     graph[second].add(first) 

# breadth-first search the graph to produce the output 
output = [] 
marked = set() # a set of all nodes whose connected component is known 
for node in graph: 
    if node not in marked: 
     # this node is not in any previously seen connected component 
     # run a breadth-first search to determine its connected component 
     frontier = set([node]) 
     connected_component = [] 
     while frontier: 
      marked |= frontier 
      connected_component.extend(frontier) 

      # find all unmarked nodes directly connected to frontier nodes 
      # they will form the new frontier 
      new_frontier = set() 
      for node in frontier: 
       new_frontier |= graph[node] - marked 
      frontier = new_frontier 
     output.append(tuple(connected_component)) 

不要僅僅複製它而不理解它;瞭解它在做什麼，或編寫自己的實現。你可能需要能夠保持這一點。 （我會使用僞代碼，但Python實際上已經和僞代碼一樣簡單了。）

如果我原來的你的問題的解釋是正確的，而你的投入是要聚集鍵值對的集合，這是我原來的答覆：

原來的答覆

import collections 

clusterer = collections.defaultdict(list) 

for l in ListA: 
    for k, v in l: 
     clusterer[k].append(v) 

output = clusterer.values() 

defaultdict(list)是dict自動創建一個list作爲這不是已經存在的任何鍵的值。循環遍歷所有元組，收集與相同鍵匹配的所有值，然後從defaultdict創建一個（key，value_list）對的列表。

（此代碼的輸出是不完全在您指定的形式，但我相信，這種形式是比較有用的，如果你想改變形式，這應該是一件簡單的事。）

Answer 2

tupleList = [(1, 2), (3, 4), (1, 4), (3, 2), (1, 2), (7, 9), (9, 8), (5, 6)] 

newSetSet = set ([frozenset (aTuple) for aTuple in tupleList]) 
setSet = set() 

while newSetSet != setSet: 
    print '*' 
    setSet = newSetSet 
    newSetSet = set() 
    for set0 in setSet: 
     merged = False 
     for set1 in setSet: 
      if set0 & set1 and set0 != set1: 
       newSetSet.add (set0 | set1) 
       merged = True 
     if not merged: 
      newSetSet.add (set0) 

     print [tuple (element) for element in setSet] 
     print [tuple (element) for element in newSetSet] 
     print 

print [tuple (element) for element in newSetSet] 

# Result: [(1, 2, 3, 4), (5, 6), (8, 9, 7)] 

Answer 3

輸出順序是否重要？這是我能想到的最簡單的方法：

ListA = [[('N1_10', 'N2_28'), ('N1_35', 'N2_44')],[('N1_22', 'N3_72'), ('N1_10', 'N3_98')], 
      [('N2_33', 'N3_28'), ('N2_55', 'N3_62'), ('N2_61', 'N3_37')]] 

idx = dict() 

for sublist in ListA: 
    for pair in sublist: 
     for item in pair: 
      mapping = idx.get(item,set()) 
      mapping.update(pair) 
      idx[item] = mapping 
      for subitem in mapping: 
       submapping = idx.get(subitem,set()) 
       submapping.update(mapping) 
       idx[subitem] = submapping 


for x in set([frozenset(x) for x in idx.values()]): 
    print list(x) 

輸出：

['N3_72', 'N1_22'] 
['N2_28', 'N3_98', 'N1_10'] 
['N2_61', 'N3_37'] 
['N2_33', 'N3_28'] 
['N2_55', 'N3_62'] 
['N2_44', 'N1_35']