Вернуть набор пар ключей из словаря, имеющих общее значение

Question

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

Пример:

Iиметь следующий словарь:

dict = {
'C': {'123'}, 
'A': {'123', '456'}, 
'D': {'123'}, 
'B': {'789', '456'}, 
'E': {'789'}}

MyFunction (dict) должен вернуть меня:

{("A", "B"), ("A", "C"), ("A", "D"), ("B", "E"), ("C", "D")}

Answer 1

Более эффективное однопроходное решение состояло бы в использовании диктовки seen, который отслеживает список ключей, которые до сих пор "видели" данное значение:

pairs = set()
seen = {}
for key, values in d.items():
    for value in values:
        if value in seen:
            for seen_key in seen[value]:
                pairs.add(frozenset((key, seen_key)))
        seen.setdefault(value, []).append(key)

pairsстанет:

{frozenset({'D', 'A'}), frozenset({'B', 'E'}), frozenset({'B', 'A'}), frozenset({'C', 'D'}), frozenset({'C', 'A'})}

Затем вы можете легко преобразовать его в набор лексикографически отсортированных кортежей, если хотите:

{tuple(sorted(p)) for p in pairs}

, который возвращает:

{('A', 'C'), ('B', 'E'), ('C', 'D'), ('A', 'D'), ('A', 'B')}

Answer 2

Использование itertools.combination :

from itertools import combinations

d = {
    'C': {'123'}, 
    'A': {'123', '456'}, 
    'D': {'123'}, 
    'B': {'789', '456'}, 
    'E': {'789'}
}

def MyFunction(d):
    out = set()
    for i, j in combinations(d, 2):
        if d[j].intersection(d[i]) and (i, j) not in out and (j, i) not in out:
            out.add((i, j))
    return set(tuple(sorted(i)) for i in out)

print(MyFunction(d))
print(MyFunction(d) == {("A", "B"), ("A", "C"), ("A", "D"), ("B", "E"), ("C", "D")})

Вывод:

{('A', 'D'), ('A', 'B'), ('B', 'E'), ('A', 'C'), ('C', 'D')}
True

Если вы считаете ('A', 'C') и ('C', 'A') одинаковыми, вы можете заменить

return set(tuple(sorted(i)) for i in out)

только с

return out

Answer 3

defaultdict + combinations

Для решения методом грубой силы вы можете инвертировать свой словарь наборов, а затем использовать понимание набора:

from collections import defaultdict
from itertools import combinations

d = {'C': {'123'}, 'A': {'123', '456'}, 
     'D': {'123'}, 'B': {'789', '456'}, 
     'E': {'789'}}

dd = defaultdict(set)

for k, v in d.items():
    for w in v:
        dd[w].add(k)

res = {frozenset(i) for v in dd.values() if len(v) >= 2 for i in combinations(v, 2)}

print(res)

{frozenset({'A', 'D'}), frozenset({'C', 'D'}),
 frozenset({'B', 'E'}), frozenset({'B', 'A'}),
 frozenset({'C', 'A'})}

Как вы можете видеть, элементы в res являются frozenset объектами, то есть они не зависят от сортировки внутри кортежей.frozenset требуется вместо set, так как set не может быть хэшируемым.