Python: get key with the least value from a dictionary BUT multiple minimum values

Question

I'm trying to do the same as Get the key corresponding to the minimum value within a dictionary, where we want to get the key corresponding to the minimum value in a dictionary.

The best way appears to be:

min(d, key=d.get)

BUT I want to apply this on a dictionary with multiple minimum values:

d = {'a' : 1, 'b' : 2, 'c' : 1}

Note that the answer from the above would be:

>>> min(d, key=d.get)
'a'

However, I need both the two keys that have a minimum value, namely a and c.

What would be the best approach?

(Ultimately I want to pick one of the two at random, but I don't think this is relevant).

Cilla

You know that since dict are not sorted, you're already picking a "random" one between those two? – Zacarias

@Rik Poggi, if you define "random" as "unspecified ordering". – Color

@DarenThomas: The words not sorted and random between double quotes were used exactly for that. – Zacarias

Answer 1

One simple option is to first determine the minimum value, and then select all keys mapping to that minimum:

min_value = min(d.itervalues())
min_keys = [k for k in d if d[k] == min_value]

For Python 3 use d.values() instead of d.itervalues().

This needs two passes through the dictionary, but should be one of the fastest options to do this anyway.

Using reservoir sampling, you can implement a single pass approach that selects one of the items at random:

it = d.iteritems()
min_key, min_value = next(it)
num_mins = 1
for k, v in it:
    if v < min_value:
        num_mins = 1
        min_key, min_value = k, v
    elif v == min_value:
        num_mins += 1
        if random.randrange(num_mins) == 0:
            min_key = k

After writing down this code, I think this option is of rather theoretical interest… :)

Ope

Answer 2

EDITED: Now using setdefault as suggested :)

I don't know if that helps you but you could build a reverse dictionary with the values as key and the keys (in a list as values).

d = {'a' : 1, 'b' : 2, 'c' : 1}
d2 = {}
for k, v in d.iteritems():
    d2.setdefault(v, []).append(k)
print d2[min(d2)]

It will print this:

['a', 'c']

However, I think the other solutions are more compact and probably more elegant...

Invercargill

You want dict.setdefault there so you don't have to do the separate assignment. – Dehnel

Thanks, did not even know it exists :) – Invercargill

Answer 3

min_keys = [k for k in d if all(d[m] >= d[k] for m in d)]

or, slightly optimized

min_keys = [k for k, x in d.items() if not any(y < x for y in d.values())]

It's not as efficient as other solutions, but demonstrates the beauty of python (well, to me at least).

Hesperides

This runs indeed in O(n^2) when there is a simple solution in O(n) (Sven Marnach's). – Macintyre

Answer 4

def get_rand_min(d):
    min_val = min(d.values())
    min_keys = filter(lambda k: d[k] == min_val, d)
    return random.choice(min_keys)

Triclinium

Answer 5

You can use heapq.nsmallest to get the N smallest members of the dict, then filter out all that are not equal to the lowest one. That's provided you know the maximal number of smallest members you can have, let's assume it's N here. something like:

from heapq import nsmallest
from operator import itemgetter

#get the N smallest members
smallestN = nsmallest(N, myDict.iteritems(), itemgetter(1)))

#leave in only the ones with a score equal to the smallest one
smallest = [x for x in smallestN if x[1] == smallestN[0][1]]

Speroni

Answer 6

This works:

d = {'a' :1, 'b' : 2, 'c' : 1}
min_value = min(d.values())
result = [x[0] for x in d.items() if x[1] == k]

Hmpf. After fixing up the code to work, I ended up with @Sven Marnach's answer, so, disregard this ;)

Color

oh, right. I tested with the second version (k = min(d.values()) I have updated my answer to fix this. – Color

Answer 7

minValue,minKey = min((v,k) for k,v in d.items())

Due to your semantics you need to go through the entire dictionary at least once. This will retrieve exactly 1 minimum element.

If you want all the minimum items in O(log(N)) query time, you can insert your elements into a priority queue as you generate them (if you can). The priority queue must have O(1) insertion time and O(log(N)) extract-min time. (This will be as bad as sorting if all your elements have the same value, but otherwise may work quite well.)

Tachometer

Answer 8

Here's another way to do it in one pass:

d = {'foo': 2, 'a' : 1, 'b' : 2, 'c' : 1, 'z': 99, 'x': 1}
current_min = d[d.keys()[0]]
min_keys = []
for k, v in d.iteritems():
    if v < current_min:
        current_min = v
        min_keys = [k]
    elif v == current_min:
        min_keys.append(k)
print min_keys
['a', 'x', 'c']

Diploid

Answer 9

One pass solution would be:

 >>> result = [100000, []]
>>> for key, val in d.items():
...  if val < result[0]:
...   result[1] = [key]; result[0]=val;
...  elif val == result[0]:
...   result[1].append(key)
... 
>>> result
[1, ['a', 'c']]

Ascocarp

100000 is not robust. float("inf") would be. – Macintyre