Alex Rivera | Logout

Select random item with weight

Asked 2012-02-13T11:49:48.757
9

I have a list of approx. 10000 items. The current situation is that every item has an associated weight (priority or importance). Now the smallest weight is -100 (negative and zero values can be removed) and the highest weight is 1500. Weight is determined by intuition by people (how somebody thinks the item is important to community). Because it's not easy to determine the most important item, I'd like to use some random factor, so that items with lower weight will have less chance to be chosen and their weight will be adjusted in the future (some mix of common sense and randomness).

Do you know how to code a function getItem?

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's my idea is to sum up the weights of all items and then compute
  # some ratios. But maybe you have better idea.
  return randomItem

Thank you

Edit
Report

1 Answer

2

It's easier to do if the weights are not negative. If you have to have negative weights, you'll have to offset the weights by the lowest possible weight. In your case, offsetted_weight = itemweight + 100

In pseudocode, it goes 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
answered 2012-02-13T11:57:58.403

Your Answer