Random from Python Dict with lowest values as priority

Question

Couldn't find this on Google so if anyone can help. I have a dict like this:

{8: 0, 5: 0, 6: 1, 4: 2, 7: 3, 9: 2, 11: 1, 10: 3}

Now I need to take 3 keys out of this dict randomly but also, here is the tricky part, take in consideration their value while doing that. Concretely I want keys that have lower values assigned to them to have bigger priority in random, so in short don't give me a key with value 2/3 if there are 3 keys with values 0/1 available. Now I know I can just sort them by value and take 3 lowest, but that would be predictable so I need any kind of randomizer in here together with taking the lowest ones available. I hope I made some sense... any ideas? Thanks in advance!

You could apply [How can I make a random selection from an inversely-weighted list?](http://stackoverflow.com/q/7762569) to make the invert the weights. — Martijn Pieters, Dec 10 '13 at 17:21
Last but not least, you want a weighted *sample*, not just one value, so look at [Weighted random sample in python](http://stackoverflow.com/q/13047806) — Martijn Pieters, Dec 10 '13 at 17:26
Ah, you want a random weighted sample *without replacement*, so use [Select random k elements from a list whose elements have weights](http://stackoverflow.com/q/2140787) — Martijn Pieters, Dec 10 '13 at 17:45
I apologize for not seeing this was answered before in some way, bad Googling on my side. 1st answer showed me all I needed since indeed all I needed to look is weighted random. Thanks everyone for the help and sry again! — MaRiNkO, Dec 10 '13 at 22:25

score 1 · Accepted Answer · edited May 23 '17 at 11:57

Combining Select k random elements from a list whose elements have weights with How can I make a random selection from an inversely-weighted list? and applied to your dictionary:

import random
from operator import mul

class Node:
    __slots__ = ['w', 'v', 'tw']
    def __init__(self, w, v, tw):
        self.w, self.v, self.tw = w, v, tw

def rws_heap(items):
    h = [None]
    for w, v in items:
        h.append(Node(w, v, w))
    for i in range(len(h) - 1, 1, -1):
        h[i>>1].tw += h[i].tw
    return h

def rws_heap_pop(h):
    gas, i = h[1].tw * random.random(), 1
    while gas > h[i].w:
        gas -= h[i].w
        i <<= 1
        if gas > h[i].tw:
            gas -= h[i].tw
            i += 1
    w, v = h[i].w, h[i].v
    h[i].w = 0
    while i:
        h[i].tw -= w
        i >>= 1
    return v

def random_weighted_sample_no_replacement(items, n):
    heap = rws_heap(items)
    for i in range(n):
        yield rws_heap_pop(heap)

def random_weighted_sample_no_replacements_inverse_weights(mapping, n):
    keys, values = zip(*mapping.items())
    total = reduce(mul, (v + 1 for v in values))
    weights = (total / (v + 1) for v in values)
    heap = rws_heap(zip(weights, keys))
    for i in xrange(n):
        yield rws_heap_pop(heap)

I condensed Jason's Python implementation a little, and inverted your weights by using multiplication (shifting all weights up by 1 to allow for the division trick).

Applying this to your dictionary:

>>> list(random_weighted_sample_no_replacements_inverse_weights(d, 3))
[9, 11, 8]
>>> list(random_weighted_sample_no_replacements_inverse_weights(d, 3))
[8, 6, 9]
>>> list(random_weighted_sample_no_replacements_inverse_weights(d, 3))
[4, 8, 5]
>>> list(random_weighted_sample_no_replacements_inverse_weights(d, 3))
[4, 10, 11]
>>> list(random_weighted_sample_no_replacements_inverse_weights(d, 3))
[4, 9, 10]
>>> list(random_weighted_sample_no_replacements_inverse_weights(d, 3))
[5, 10, 8]
>>> list(random_weighted_sample_no_replacements_inverse_weights(d, 3))
[6, 4, 5]

where 8 and 5 show up more often than 7 and 11.

Random from Python Dict with lowest values as priority

1 Answers1