Inverting one-to-many mapping using dictionary comprehension

user_16742496 0
Viewed 103
lst = [{'272': '4', '273': '4', '274': '4', '275': '5'}]
dct = {}

for k, v in lst[0].items():
    if dct.get(v) is None:
        dct.update({v: [k]})
    else:
        dct[v].append(k)

Output:

{'4': ['272', '273', '274'], '5': ['275']}

I can also write a nested comprehension:

dct = {v: [k for (k, v1) in lst[0].items() if v1 == v]
          for (k, v) in lst[0].items()}

Output is same:

{'4': ['272', '273', '274'], '5': ['275']}**

But can we try to acheive the same result by using a single for loop in the dict comprehension?

python-3.x list dictionary python
2 Answers

You can't quite do the same thing in a dict comprehension in one step. You're effectively inverting the dictionary, but since you don't have a 1-to-1 mapping in the original, you need to aggregate repeated keys for each value.

The list in the question is a red herring. I am going to use

d = {'272': '4', '273': '4', '274': '4', '275': '5'}

There are a couple of approaches you can take. The sane one is to keep a loop, but simplify it slightly. For example, you could use collections.defaultdict, which is like a regular dict, except it lets you automatically set missing keys with empty values:

from collections import defaultdict

result = defaultdict(list)
for k, v in d.items():
    result[v].append(k)

You can write a comprehension for this if you use a couple of standard library functions though. One way is to use itertools.groupby, but that requires you to apply sorted first:

from itertools import groupby
from operator import itemgetter

result = {k: list(map(itemgetter(0), vs))
              for k, vs in groupby(sorted(d.items(),
                                          key=itemgetter(1, 0)),
                                   itemgetter(1))}

operator.itemgetter works like lambda x: x[0] or so here, but faster and more efficiently.

With the second solution, note that the time complexity went from O(n) to O(n log n) because of the sort, and you sacrifice a lot of legibility just to have a "one-liner".

user_29887300

A hack with a temporary helper dictionary:

dct = {v: h.setdefault(v, [k])
       for h in [{}]
       for k, v in lst[0].items()
       if v not in h or h[v].append(k)}
user_167591160
Related