Compare unordered list of dynamic dicts

Question

Is and if so how, is it possible to compare the equality of an unordered list o dictionaries with dynamic keys & values?

dict_list_1 = [ {'a': 'b'}, {'c': 'd'} ] 
dict_list_2 = [ {'c': 'd'}, {'a': 'b'} ]
dict_list_3 = [ {'c': 'd'}, {'d': 'c'} ]

where dict_list_1 and dict_list_2 should be considered equal and dict_list_3 shouldnt be equal to any of the other 2

The keys (and values) of the dicts are dynamic so sorting gets a bit harder

Current code for comparing equality of 2 dicts:

for a in dict_1.keys():
    try:
        if dict_1[a] != dict_2[a]:
            return False
        # recursive in case of dict within dict
        if not equal_dict_values(dict_1[a], dict_2[a]):
            return False
    except KeyError:
        return False
return True

But I'm not quite sure how to approach the unordered list of dicts problem.

you could start off with sorting by keys and then check the equality — DirtyBit, Sep 03 '20 at 12:12
@superbrain in this example `dict_list_1 == dict_list_2 = False` but I want it to output `True` — Ivar Reukers, Sep 03 '20 at 12:13
@DirtyBit how can we sort by keys if not all dicts might have the key and the keys are not set in stone? — Ivar Reukers, Sep 03 '20 at 12:14
You might be able to use `collections.ChainMap`. `ChainMap(*dict_list_1) == ChainMap(*dict_list_2)` is `True`; it's false for other pairs of distinct arguments. — chepner, Sep 03 '20 at 12:18
@chepner This will fail for e.g. `[{1: 2, 3: 4}, {5: 6}]` and `[{1: 2}, {3: 4, 5: 6}]`, but should work if all the dictionaries have only one key/value pair as in the example. — kaya3, Sep 03 '20 at 13:15
@Chris This will fail for e.g. `[{1: 2}, {1: 3}]` and `[{1: 3}, {1: 2}]`. — kaya3, Sep 03 '20 at 13:17
Does this answer your question? [How to efficiently compare two unordered lists (not sets) in Python?](https://stackoverflow.com/questions/7828867/how-to-efficiently-compare-two-unordered-lists-not-sets-in-python) — Tomerikoo, Sep 03 '20 at 13:26
"The keys (and values) of the dicts are dynamic so sorting gets a bit harder" Can you clarify what you mean by that? Do you mean you don't know the dict keys *by which* to sort? Do you mean the dicts may change during comparison? — MisterMiyagi, Sep 03 '20 at 13:37

score 0 · Accepted Answer · answered Sep 03 '20 at 13:28

Here's a solution which should work generally, even when the list has multiples of the same dictionary, and when the dictionaries in one list can have common keys. The idea is to convert the dictionaries into a canonical, hashable form, and then compare them as bags (sets which can contain multiples) using Counter.

It does assume that the dictionary keys are comparable and the dictionary values are hashable, so it won't work if you have dictionaries with incomparable keys or unhashable values.

from collections import Counter

def dict_to_canonical_hashable(d):
    return tuple(sorted(d.items()))

def unordered_lists_equal(a, b):
    canonical_a = Counter(map(dict_to_canonical_hashable, a))
    canonical_b = Counter(map(dict_to_canonical_hashable, b))
    return canonical_a == canonical_b

Tests:

>>> unordered_lists_equal(dict_list_1, dict_list_2)
True
>>> unordered_lists_equal(dict_list_1, dict_list_3)
False
>>> unordered_lists_equal(dict_list_2, dict_list_3)
False
>>> unordered_lists_equal([{1: 2, 3: 4}, {5: 6}], [{1: 2}, {3: 4, 5: 6}])
False
>>> unordered_lists_equal([{1: 2}, {1: 3}], [{1: 3}, {1: 2}])
True
>>> unordered_lists_equal([{1: 2}, {1: 2}], [{1: 2}])
False
>>> unordered_lists_equal([{1: 2}, {1: 2}], [{1: 2}, {1: 2}])
True

One asterisk here - `sorted` is required as of v 3.6+, before that it doesn't make a difference. — Grzegorz Skibinski, Sep 04 '20 at 09:08
@GrzegorzSkibinski `sorted` is needed in all versions of CPython, because of hash collisions; try `tuple({32: 1, 64: 2}.items())` and `tuple({64: 2, 32: 1}.items())` in Python 3.5, for example. — kaya3, Sep 04 '20 at 12:05

Compare unordered list of dynamic dicts

1 Answers1