Как слить несколько словарей из отдельных списков, если они разделяют пары ключей?

Question

Как объединить словари из нескольких списков, если они имеют общую пару ключ-значение?

К примеру, здесь есть три списка словарей:

l1 = [{'fruit':'banana','category':'B'},{'fruit':'apple','category':'A'}] 
l2 = [{'type':'new','category':'A'},{'type':'old','category':'B'}] 
l3 = [{'order':'2','type':'old'},{'order':'1','type':'new'}] 

Желаемый результат:

l = [{'fruit':'apple','category':'A','order':'1','type':'new'},{'fruit':'banana','category':'B','order':'2','type':'old'}] 

Хитрость в том, что я хочу эту функцию, чтобы принимать только в списках в качестве аргументов и не ключи, потому что я хочу только подключить любое количество списков словарей и не беспокоиться о том, какие ключевые имена являются перекрывающимися (в этом случае ключевыми именами, которые объединяют всех трех, являются «категория» и «категория», тип').

Следует отметить, что индекс не должен иметь значения, поскольку он должен основываться только на общих элементах.

Вот моя попытка:

def combine_lists(*args): 
    base_list = args[0] 
    L = [] 
    for sublist in args[1:]: 
     L.extend(sublist) 
    for D in base_list: 
     for Dict in L: 
      if any([tup in Dict.items() for tup in D.items()]): 
       D.update(Dict) 
    return base_list 

Answer 1

Для этой задачи удобно рассматривать dicts как списки кортежей:

In [4]: {'fruit':'apple','category':'A'}.items() 
Out[4]: [('category', 'A'), ('fruit', 'apple')] 

Поскольку мы хотим подключить dicts, которые разделяют пару ключ-значение , мы можем рассматривать каждый кортеж как узел в графе и пары кортежей как ребра. Когда у вас есть график , проблема сводится к поиску подключенных компонентов графика.

Использование networkx,

import itertools as IT 
import networkx as nx 

l1 = [{'fruit':'apple','category':'A'},{'fruit':'banana','category':'B'}] 
l2 = [{'type':'new','category':'A'},{'type':'old','category':'B'}] 
l3 = [{'order':'1','type':'new'},{'order':'2','type':'old'}] 

data = [l1, l2, l3] 
G = nx.Graph() 
for dct in IT.chain.from_iterable(data): 
    items = list(dct.items()) 
    node1 = node1[0] 
    for node2 in items: 
     G.add_edge(node1, node22) 

for cc in nx.connected_component_subgraphs(G): 
    print(dict(IT.chain.from_iterable(cc.edges()))) 

дает

{'category': 'A', 'fruit': 'apple', 'type': 'new', 'order': '1'} 
{'category': 'B', 'fruit': 'banana', 'type': 'old', 'order': '2'} 

---

Если вы хотите, чтобы удалить NetworkX зависимость, можно использовать, например, pillmuncher's implementation:

import itertools as IT 

def connected_components(neighbors): 
    """ 
    https://stackoverflow.com/a/13837045/190597 (pillmuncher) 
    """ 
    seen = set() 
    def component(node): 
     nodes = set([node]) 
     while nodes: 
      node = nodes.pop() 
      seen.add(node) 
      nodes |= neighbors[node] - seen 
      yield node 
    for node in neighbors: 
     if node not in seen: 
      yield component(node) 

l1 = [{'fruit':'apple','category':'A'},{'fruit':'banana','category':'B'}] 
l2 = [{'type':'new','category':'A'},{'type':'old','category':'B'}] 
l3 = [{'order':'1','type':'new'},{'order':'2','type':'old'}] 

data = [l1, l2, l3] 
G = {} 
for dct in IT.chain.from_iterable(data): 
    items = dct.items() 
    node1 = items[0] 
    for node2 in items[1:]: 
     G.setdefault(node1, set()).add(node2) 
     G.setdefault(node2, set()).add(node1) 

for cc in connected_components(G): 
    print(dict(cc)) 

, который печатает тот же результат, что и выше.