algorithm - Generate pairs having the same attributes from list -

assume have list of items, each set of attributes.

what efficient algorithm generating pairs list having same attributes?

for example, given list:

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

we should return following list of 4 pairs, out of total possible six:

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

now, trivial approach first generate list of possible n(n+1)/2 pairs, , filter out without similar attributes, suspect approach inefficient, if number of pairs large.

any suggestions?

i suggest 2 phase algorithm:

arr = [('item1', {'a','b'}), ('item2', {'a'}), ('item3', {'c','b'}), ('item4', {'b'})]  # 1. create map each attribute list of items have mp = {} lst in arr:     prop in lst[1]:         if prop not in mp: mp[prop] = []         mp[prop].append(lst[0])  # 2. each attribute: add pairs of items result set result = set() prop in mp:     items = mp[prop]     # collect pairs in items list     p1 in range(len(items)):         p2 in range(p1+1,len(items)):             result.add((items[p1],items[p2]))  print (result) 

output:

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