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. Please suggest me an easy and efficient way to do it.

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).

If you don't actually need a dict at the end of the day, you could use itertools.groupby:

from itertools import groupby
from operator import itemgetter

for k, v in groupby(sorted(d.items(), key=itemgetter(1)), itemgetter(1)):
    print(k, list(map(itemgetter(0), v)))

Of course, you could use this to construct a dict if you really wanted to:

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

But at that point, you're probably better off using Martijn's defaultdict solution.