合併元組，如果他們有一個共同的元素

Question

考慮以下列表：

tuple_list = [('c', 'e'), ('c', 'd'), ('a', 'b'), ('d', 'e')] 

我怎樣才能做到這一點？

new_tuple_list = [('c', 'e', 'd'), ('a', 'b')] 

我曾嘗試：

for tuple in tuple_list: 
    for tup in tuple_list: 
     if tuple[0] == tup[0]: 
      new_tup = (tuple[0],tuple[1],tup[1]) 
      new_tuple_list.append(new_tup) 

但是，如果我有數組的元素按照一定的順序，這意味着它會導致此相反，它僅適用：

new_tuple_list = [('c', 'e', 'd'), ('a', 'b'), ('d', 'e')] 

Answer 1

您可以將元組視爲圖中的邊，並且您的目標是在圖中找到connected components。那麼你可以在頂點簡單循環（元組中的項目），併爲每個頂點你沒有訪問過尚未執行DFS生成組件：以上兩種

[['a', 'b'], ['c', 'e', 'd']] 

注意在：

from collections import defaultdict 

def dfs(adj_list, visited, vertex, result, key): 
    visited.add(vertex) 
    result[key].append(vertex) 
    for neighbor in adj_list[vertex]: 
     if neighbor not in visited: 
      dfs(adj_list, visited, neighbor, result, key) 

edges = [('c', 'e'), ('c', 'd'), ('a', 'b'), ('d', 'e')] 

adj_list = defaultdict(list) 
for x, y in edges: 
    adj_list[x].append(y) 
    adj_list[y].append(x) 

result = defaultdict(list) 
visited = set() 
for vertex in adj_list: 
    if vertex not in visited: 
     dfs(adj_list, visited, vertex, result, vertex) 

print(result.values()) 

輸出組件中的組件和元素是隨機的。

Answer 2

這有一個壞的性能，因爲列表包含檢查是O(n)但它是很短：

result = [] 

for tup in tuple_list: 
    for idx, already in enumerate(result): 
     # check if any items are equal 
     if any(item in already for item in tup): 
      # tuples are immutable so we need to set the result item directly 
      result[idx] = already + tuple(item for item in tup if item not in already) 
      break 
    else: 
     # else in for-loops are executed only if the loop wasn't terminated by break 
     result.append(tup) 

這有很好的副作用是，爲了保持：

>>> result 
[('c', 'e', 'd'), ('a', 'b')] 

Answer 3

使用套。你檢查重疊，（最初是小）積累套，和Python有一個數據類型：

#!python3 

#tuple_list = [('c', 'e'), ('c', 'd'), ('a', 'b'), ('d', 'e')] 
tuple_list = [(1,2), (3,4), (5,), (1,3,5), (3,'a'), 
     (9,8), (7,6), (5,4), (9,'b'), (9,7,4), 
     ('c', 'e'), ('e', 'f'), ('d', 'e'), ('d', 'f'), 
     ('a', 'b'), 
     ] 
set_list = [] 

print("Tuple list:", tuple_list) 
for t in tuple_list: 
    #print("Set list:", set_list) 
    tset = set(t) 
    matched = [] 
    for s in set_list: 
     if tset & s: 
      s |= tset 
      matched.append(s) 

    if not matched: 
     #print("No matches. New set: ", tset) 
     set_list.append(tset) 

    elif len(matched) > 1: 
     #print("Multiple Matches: ", matched) 
     for i,iset in enumerate(matched): 
      if not iset: 
       continue 
      for jset in matched[i+1:]: 
       if iset & jset: 
        iset |= jset 
        jset.clear() 

set_list = [s for s in set_list if s] 
print('\n'.join([str(s) for s in set_list])) 

Answer 4

如果您不需要重複值（能夠保持['a', 'a', 'b']，例如），這是一種簡單，快捷的方式，做你通過設置想要的東西：

iset = set([frozenset(s) for s in tuple_list]) # Convert to a set of sets 
result = [] 
while(iset):     # While there are sets left to process: 
    nset = set(iset.pop())  # Pop a new set 
    check = len(iset)   # Does iset contain more sets 
    while check:    # Until no more sets to check: 
     check = False 
     for s in iset.copy():  # For each other set: 
      if nset.intersection(s): # if they intersect: 
       check = True   # Must recheck previous sets 
       iset.remove(s)   # Remove it from remaining sets 
       nset.update(s)   # Add it to the current set 
    result.append(tuple(nset)) # Convert back to a list of tuples 

給

[('c', 'e', 'd'), ('a', 'b')]