Pythonic inverse dict non-unique mappings

Question

I have a dictionary like this:

dict1 = {'a':[1,2,3], 'b':[1,2,3,4], 'c':[1,2]}

and want the inverse like this:

dict2 = dict({1:['a','b','c'], 2:['a','b','c'], 3:['a','b'], 4:['b']})

Like these questions:

Inverse Dict in Python \\ In-place dictionary inversion in Python

But I want to do it with non-unique keys and I don't want in-place conversion. I have some code working, but I was wondering if there's a dictionary comprehension way of doing this.

from collections import defaultdict
dict2 = defaultdict(list)
for i in dict1:
    for j in dict1[i]:
        dict2[j].append(i)

I tried this, but it only works for unique mappings. By unique I mean something like "for each value, there is only one key under which the value is listed". So unique mapping: '1: [a], 2: [b], 3: [c] -> a: [1], b: [2], c: [3]' VS non-unique mapping '1: [a], 2: [a, b], 3: [b, c] -> a: [1, 2], b: [2, 3], c: [3]'

dict2 = {j: i for i in dict1 for j in dict1[i]}

I think it must be something like this:

dict2 = {j: [i for i in dict1 if j in dict1[i]] for j in dict1[i]} # I know this doesn't work

Besides it not working, it seems like a comprehension like this would be inefficient. Is there an efficient, one liner way of doing this?

Answer 1

I figured out an answer based on Vroomfondel's answer:

dict1 = {'a':[1,2,3], 'b':[1,2,3,4], 'c':[1,2]}
dict2 = {item: [key for key in dict1 if item in dict1[key]] for value in dict1.values() for item in value}

This isn't the fastest, but it is a one liner and it is not the slowest of the options presented!

from timeit import timeit

methods = [['Vroomfondel1', '''from collections import defaultdict
import itertools
dict1 = {'a':[1,2,3], 'b':[1,2,3,4], 'c':[1,2]}
dict2 = defaultdict(list)
for k,v in itertools.chain.from_iterable([itertools.product(vals,key) for key,vals in dict1.items()]):
    dict2[k].append(v)'''],

['Vroomfondel2', '''from collections import defaultdict
import itertools
dict1 = {'a':[1,2,3], 'b':[1,2,3,4], 'c':[1,2]}
dict2 = defaultdict(list)
[dict2[k].append(v) for k,v in itertools.chain.from_iterable([itertools.product(vals,key) for key,vals in dict1.items()])]'''],


['***Vroomfondel2 mod', '''dict1 = {'a':[1,2,3], 'b':[1,2,3,4], 'c':[1,2]}
dict2 = {item: [key for key in dict1 if item in dict1[key]] for value in dict1.values() for item in value}'''],

['mhlester1', '''dict1 = {'a':[1,2,3], 'b':[1,2,3,4], 'c':[1,2]}
dict2 = {}
for key, values in dict1.items():
    for value in values:
        dict2.setdefault(value, []).append(key)'''],

['mhlester1 mod', '''from collections import defaultdict
dict1 = {'a':[1,2,3], 'b':[1,2,3,4], 'c':[1,2]}
dict2 = defaultdict(list)
for key, values in dict1.items():
    for value in values:
        dict2[value].append(key)'''],

['mhlester2', '''from collections import defaultdict
dict1 = {'a':[1,2,3], 'b':[1,2,3,4], 'c':[1,2]}
dict2 = defaultdict(list)
for key, values in dict1.items():
    for value in values:
        dict2[value].append(key)'''],

['initial', '''from collections import defaultdict
dict1 = {'a':[1,2,3], 'b':[1,2,3,4], 'c':[1,2]}
dict2 = defaultdict(list)
for i in dict1:
    for j in dict1[i]:
        dict2[j].append(i)''']

]

for method in methods:
    print "% 15s" % (method[0]), '\t', timeit(method[1], number=10000)

prints out:

   Vroomfondel1     0.202519893646
   Vroomfondel2     0.164724111557
***Vroomfondel2 mod     0.114083051682
      mhlester1     0.0599339008331
  mhlester1 mod     0.091933965683
      mhlester2     0.0900268554688
        initial     0.0953099727631

Answer 2

Standard dict:

>>> dict2 = {}
>>> for key, values in dict1.items():
...     for value in values:
...             dict2.setdefault(value, []).append(key)
... 
>>> dict2
{1: ['a', 'c', 'b'], 2: ['a', 'c', 'b'], 3: ['a', 'b'], 4: ['b']}

defaultdict:

>>> dict2 = defaultdict(list)
>>> for key, values in dict1.items():
...     for value in values:
...             dict2[value].append(key)
... 
>>> dict2
{1: ['a', 'c', 'b'], 2: ['a', 'c', 'b'], 3: ['a', 'b'], 4: ['b']}

Answer 3

As a one-liner (thanks to mhlesters input), but with so-so readability (and only working because the values in dict2 are mutable and thus setdefault returning a reference to them):

import itertools
[dict2.setdefault(k,[]).append(v) for k,v in itertools.chain.from_iterable([itertools.product(vals,[key]) for key,vals in dict1.items()])]

Or with a for loop:

import collections
import itertools
dict2=collections.defaultdict(list)
for k,v in itertools.chain.from_iterable([itertools.product(vals,[key]) for key,vals in dict1.items()]):
    dict2[k].append(v)