Btukfyl

How can I write a function, that would take a dictionary and return me a set that would consist of pairs of keys that have at least one common value?

Example:

I have the following dictionary:

dict = {

'C': {'123'}, 

'A': {'123', '456'}, 

'D': {'123'}, 

'B': {'789', '456'}, 

'E': {'789'}}

MyFunction(dict) should return me:

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

A more efficient one-pass solution would be to use a seen dict that keeps track of a list of keys that have "seen" a given value so far:

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 would become:

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

You can then easily transform it to a set of lexicographically sorted tuples if you want:

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

which returns:

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

Using itertools.combinations:

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")})

Output is:

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

True

If you consider ('A', 'C') and ('C', 'A') same, you can replace

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

with just

return out

defaultdict + combinations

For a brute force solution, you can invert your dictionary of sets, then use a set comprehension:

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'})}

As you can see the items in res are frozenset objects, i.e. they aren't depending on sorting within tuples. frozenset is required instead of set since set is not hashable.