Генерация пар с одинаковыми атрибутами из списка

Question

Предположим, у вас есть список предметов, каждый с набором атрибутов.

Каков эффективный алгоритм генерации всех пар из списка, имеющих одинаковые атрибуты?

Например, дан список:

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

Мы должны вернуть следующий список из четырех пар из шести возможных:

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

Теперь, тривиальный подход заключается в том, чтобы сначала создать список всех возможных n(n+1)/2 пар, а затем отфильтровывать те, у которых нет похожих атрибутов, но я подозреваю, что этот подход неэффективен, особенно если количество пар очень велико.

Какие-либо предложения?

Answer 1

Я бы предложил двухфазный алгоритм:

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)

Выход:

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