Find unique (key: value) pair given N dictionaries in python

Question

I would like to find an easy and/or fast way to find all common couple (pair: value) given N dictionaries in python. (3.X would be best)

PROBLEM

Given a set of 3 dicts (but it could be any dict, it is just for the example)

n1 = {'a': 1, 'b': 2, 'c': 3}
n2 = {'a': 1, 'b': 4, 'c': 3, 'd': 4}
n3 = {'a': 1, 'b': 2, 'c': 3, 'd': 4}

The result for common (key: values) for n1, n2 and n3 should be:

({'a': 1, 'c': 3})

And for n2 and n3 it should be

({'a': 1, 'c': 3, 'd': 4})

I first though about using a brute force algorithm that will check every pair (key: value) for every dict

Here is a implementation using a recursive algorithm

SOLUTION A

list_dict = [n1, n2, n3]

def finding_uniquness(ls):

    def recursion(ls, result):
        if not ls:
            return result
        result = {k: v  for k, v in result.items()  for k1, v1 in ls[0].items() if k == k1 and v == v1}
        return recursion(ls[1:], result)

    return recursion(ls[1:], ls[0])


finding_uniquness(list_dict)
# {'c': 3, 'a': 1}

But it is not easily understandable and the complexity is high (I'm not sure how to calculate complexity; but since we compare all the elements on all dict, the complexity should be O(N²)?)

Then, I though about Sets. because it could naturally compare all the element

SOLUTION B

import functools

list_dict = [n1, n2, n3]
set_list = [set(n.items()) for n in list_dict]

functools.reduce(lambda x, y: x & y, set_list)
 # {('a', 1), ('c', 3)}

It is so much better than the previous solution, unfortunately, when one of the key have a list as values it throws an error:

>>> n = {'a': [], 'b': 2, 'c': 3}
>>> set(n.items()) 

TypeError: unhashable type: 'list'

My question is then double:

• is there any better algorithm than SOLUTION A?
• or is there a way to avoid the TypeError with SOLUTION B?

of course, any other remarks will be welcome.

Answer 1

Simpler and more efficient way:

>>> {k: v
     for k, v in list_dict[0].items()
     if all(k in d and d[k] == v
            for d in list_dict[1:])}
{'c': 3, 'a': 1}

Using an extra variable for list_dict[1:] might be beneficial, otherwise the short-circuiting of all somewhat goes to waste. Or if you don't need the list afterwards you could just pop the "master" dictionary:

>>> {k: v
     for k, v in list_dict.pop().items()
     if all(k in d and d[k] == v
            for d in list_dict)}
{'c': 3, 'a': 1}

Or using get with a default that cannot be in the dictionary as suggested by @Jean-FrançoisFabre:

>>> marker = object()
>>> {k: v
         for k, v in list_dict.pop().items()
         if all(d.get(k, marker) == v
                for d in list_dict)}
{'c': 3, 'a': 1}