Générer des paires ayant les mêmes attributs de la liste

Question

Supposons que vous ayez une liste d'éléments, chacun avec un ensemble d'attributs.

Qu'est-ce qu'un algorithme efficace pour générant toutes les paires de la liste ayant les mêmes attributs?

Par exemple, étant donné une liste:

[('item1', {'a','b'}), ('item2', {'a'}), ('item3', {'c','b'}), ('item4', {'b'})] 

Nous devrions retourner la liste suivante de quatre paires, sur le total six possibles:

('item1', 'item2') # both have attribute 'a' 
('item1', 'item3') # both have attribute 'b' 
('item1', 'item4') # both have attribute 'b' 
('item3', 'item4') # both have attribute 'b' 

Maintenant, l'approche trivial serait d'abord générer la liste de toutes les paires n(n+1)/2 possibles, puis filtrer ceux sans attributs similaires, mais je soupçonne que cette approche est inefficace, surtout si le nombre de paires est très grand.

Des suggestions?

Answer 1

je suggère un algorithme en deux phases:

arr = [('item1', {'a','b'}), ('item2', {'a'}), ('item3', {'c','b'}), ('item4', {'b'})] 

# 1. create map with for each attribute the list of items that have it 
mp = {} 
for lst in arr: 
    for prop in lst[1]: 
     if prop not in mp: mp[prop] = [] 
     mp[prop].append(lst[0]) 

# 2. for each attribute: add the pairs of items to the result set 
result = set() 
for prop in mp: 
    items = mp[prop] 
    # collect all pairs in items list 
    for p1 in range(len(items)): 
     for p2 in range(p1+1,len(items)): 
      result.add((items[p1],items[p2])) 

print (result) 

sortie:

{('item1', 'item4'), ('item1', 'item2'), ('item3', 'item4'), ('item1', 'item3')}