Grouping Python dictionary keys as a list and create a new dictionary with this list as a value

I have a python dictionary

d = {1: 6, 2: 1, 3: 1, 4: 9, 5: 9, 6: 1}

Since the values in the above dictionary are not unique, I want to group the all the keys of unique values as a list and create a new dictionary as follows:

v = {6:[1], 1:[2, 3, 6], 9: [4, 5]}

Note the keys of new dictionary v should be sorted. I am finding it hard to visualize and implement this dictionary creation.

Answer

Using collections.defaultdict for ease:

from collections import defaultdict

v = defaultdict(list)

for key, value in sorted(d.items()):
    v[value].append(key)

but you can do it with a bog-standard dict too, using dict.setdefault():

v = {}

for key, value in sorted(d.items()):
    v.setdefault(value, []).append(key)

The above sorts keys first; sorting the values of the output dictionary later is much more cumbersome and inefficient.

If anyone would not need the output to be sorted, you can drop the sorted() call, and use sets (the keys in the input dictionary are guaranteed to be unique, so no information is lost):

v = {}

for key, value in d.items():
    v.setdefault(value, set()).add(key)

to produce:

{6: {1}, 1: {2, 3, 6}, 9: {4, 5}}

(that the output of the set values is sorted is a coincidence, a side-effect of how hash values for integers are implemented; sets are unordered structures).