Search code examples
pythondictionarymappinginverse

Python reverse / inverse a mapping (but with multiple values for each key)

This is really a variation on this question, but not a duplicate:

Python reverse / invert a mapping

Given a dictionary like so:

mydict= { 'a': ['b', 'c'], 'd': ['e', 'f'] }

How can one invert this dict to get:

inv_mydict = { 'b':'a', 'c':'a', 'e':'d', 'f':'d' }

Note that values span uniquely under each key.

Note: I previously had syntax map = ... and dict = ... Reminder not to use map and dict as they are built-in functions, see excellent comments and answers below :)

Solution

  • TL;DR

    Use dictionary comprehension, like this

    >>> my_map = { 'a': ['b', 'c'], 'd': ['e', 'f'] }
>>> {value: key for key in my_map for value in my_map[key]}
{'c': 'a', 'f': 'd', 'b': 'a', 'e': 'd'}

    The above seen dictionary comprehension is functionally equivalent to the following looping structure which populates an empty dictionary

    >>> inv_map = {}
>>> for key in my_map:
...     for value in my_map[key]:
...         inv_map[value] = key
... 
>>> inv_map
{'c': 'a', 'f': 'd', 'b': 'a', 'e': 'd'}

    Note: Using map shadows the built-in map function. So, don't use that as a variable name unless you know what you are doing.

    Other similar ways to do the same

    Python 3.x

    You can use dict.items, like this

    >>> {value: key for key, values in my_map.items() for value in values}
{'c': 'a', 'f': 'd', 'b': 'a', 'e': 'd'}

    We use items() method here, which would create a view object from the dictionary which would give key value pairs on iteration. So we just iterate over it and construct a new dictionary with the inverse mapping.

    Python 2.x

    You can use dict.iteritems like this

    >>> {value: key for key, values in my_map.iteritems() for value in values}
{'c': 'a', 'b': 'a', 'e': 'd', 'f': 'd'}

    We don't prefer items() method in 2.x, because it will return a list of key-value pairs. We don't want to construct a list just to iterate and construct a new dictionary. That is why we prefer iteritems(), which returns an iterator object which gives a key value pair on iteration.

    Note: The actual equivalent of Python 3.x's items would be Python 2.x's viewitems method, which returns a view object. Read more about the view object in the official documentation, here.

    iter* vs view* methods in Python 2.x

    The main difference between iter* functions and view* functions in Python 2.x is that, the view objects reflect the current state of the dictionary. For example,

    >>> d = {1: 2}
>>> iter_items = d.iteritems()
>>> view_items = d.viewitems()

    now we add a new element to the dictionary

    >>> d[2] = 3

    If you try to check if (2, 3) (key-value pair) is in the iter_items, it will throw an error

    >>> (2, 3) in iter_items
Traceback (most recent call last):
  File "<input>", line 1, in <module>
RuntimeError: dictionary changed size during iteration

    but view object will reflect the current state of the dictionary. So, it will work fine

    >>> (2, 3) in view_items
True