Search code examples
pythondictionaryreverseone-liner

One liner to revert dictionary with non-unique values with O(n) complexity

Is it possible to produce one liner (i.e. comprehension) with better time complexity than O(n²) as below?

my_map = {'A': 'x',
          'B': 'y',
          'C': 'x',
          'D': 'z'}

rev_map = {b: [a2 for a2 in my_map.keys() if my_map[a2] == b]
           for a, b in my_map.items()}

Have not found any in related Reverse / invert a dictionary mapping.

Solution

  • The issue isn't one-liners. The problem is that comprehensions are for expressing mapping/filtering operations. And you cannot get an O(N) implementation of this using map/filter. You need a reduce. Of course, to keep it on one line, with a lambda expression, it will be hacky and ugly:

    And the one-liner:

    reduce(lambda d, k: [d.setdefault(my_map[k], []).append(k), d][1], my_map, {})

    In the REPL:

    >>> my_map = {'A': 'x',
...           'B': 'y',
...           'C': 'x',
...           'D': 'z'}
>>> import functools
>>> functools.reduce(lambda d, k: [d.setdefault(my_map[k], []).append(k), d][1], my_map, {})
{'x': ['A', 'C'], 'y': ['B'], 'z': ['D']}

    But please don't use this. Just write the regular for-loop.