Choose a random item with a weight

Question

I have a list of approx. 10,000 items. The current situation is that each element has an associated weight (priority or importance). Now the smallest weight is -100 (negative and zero values ​​can be removed), and the maximum weight is 1500 . Weight is determined by people's intuition (as someone thinks this subject is important to the community). Since it is not easy to determine the most important element, I would like to use some random factor, so that objects with lower weight will have less chance of choice, and their weight will be adjusted in the future (some combinations of common sense and randomness).

Do you know how to code the getItem function?

 def getItem(dict): # this function should return random item from # the dictionary of item-weight pairs (or list of tuples) # Normally I would return only random item from the dictionary, # but now I'd like to have this: The item with weight 1500 should # have much more chance to be returned than the item with weight 10. # What my idea is to sum up the weights of all items and then compute # some ratios. But maybe you have better idea. return randomItem 

thanks

Answer 1

Take a look at this, I think you need some good comparison between the various methods. Weighted random generation in Python

The easiest approach:

 import random def weighted_choice(weights): totals = [] running_total = 0 for w in weights: running_total += w totals.append(running_total) rnd = random.random() * running_total for i, total in enumerate(totals): if rnd < total: return i 

In the link above you can find more detailed information and possible improvements, as well as several different approaches.

Answer 2

You must extract a random number between 0 and the sum of the weights (positive by definition). Then you get the item from the list using bisect: http://docs.python.org/library/bisect.html (standard text for bisect).

 import random import bisect weight = {'a':0.3,'b':3.2,'c':2.4} items = weight.keys() mysum = 0 breakpoints = [] for i in items: mysum += weight[i] breakpoints.append(mysum) def getitem(breakpoints,items): score = random.random() * breakpoints[-1] i = bisect.bisect(breakpoints, score) return items[i] print getitem(breakpoints,items) 

Answer 3

This is easier to do if the weights are not negative. If you must have negative weights, you will have to compensate for the scales with the lowest weight. In your case, offsetted_weight = itemweight + 100

In pseudo code, it looks like this:

 Calculate the sum of all the weights. Do a random from 0 to the sum of the weights Set i to 0 While the random number > 0 Subtract the weight of the item at index i from random If the random number is < 0 return item[i] Add 1 to i 

Answer 4

If you save your data in a database, you can use SQL:

 SELECT * FROM table ORDER BY weight*random() DESC LIMIT 1