合并元组，如果他们有一个共同的元素

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