Weighted shuffle of dictionary by weight of value

user_6346482 0
Viewed 59

I have a dictionary which has elements to sort as keys and their weights / probabilities as values.

I would like to get a sorted list of keys using the values as probability to be the next element chosen.

Example:

l = {6: 5859, 7: 61636, 2: 53317}

# Example output 1
output1 = [7,2,6]
# Example output 2
output2 = [2,7,6]

I researched a bit and found the sort function redefining it and multiplying random() with the weight itself, but I do not get the syntax to run. So my "pseudo code" python solution is:

from random import random
l.sort(key = lambda element: random() * element.value())

Of course, a dictionary does not have a sort function and element.value() does not work, but this is how I think it could work with better syntax.

Or is there a better solution?

python-3.x dictionary sorting
1 Answers

If you want to sort an iterable which is not a list, either convert it to a list first, or call sorted on it directly.

For instance, if d is a dict, then you can sort its keys using:

  • a = sorted(d.keys()); or
  • a = list(d); a.sort().

Since you need both the keys and the values, you should work on d.items() rather than on d.keys(). Then, if the key function you pass to sorted is defined as lambda x: ..., you can refer to the dict key as x[0] and the dict value as x[1].

I seem to understand that a higher weight should increase the probability that a number will come first. In that case, you should use optional argument reverse=True of sorted, to sort in decreasing order rather than in increasing order.

With all this in mind, fixing your code:

import random

d = {6: 5859, 7: 61636, 2: 53317}

a = [k for k,v in sorted(d.items(), key=lambda x: random.uniform(0, x[1]), reverse=True)]

print(a)
# [7, 2, 6]
user_30807230
Related