Weighted Item Algorithm

Question

Hi everyone,

I would like to learn how to select weighted items. For example : I want to fetch questions from a pool but if some one can't give right answer to a question, that causes this question to double its weight and increase the probability of being selected again later on.

Answer 1

Keep around an array of the candidate items. If one item has weight 2, put it in the array twice, generally if one has weight n put it in there n times. Then select a random element from the array. Ta-daaa.

Answer 2

Have a look at this this(scroll down for the code).

EDIT for the critics:)

The code on this thread I linked shows how to implement a binary tree approach that actually works with weights and doesn't store masses of elements in an array to achieve a weighted probability. Then again, it's pretty inefficient when the weights change very often as the binary tree has to be re-created every time a weight changes.

EDIT2:

See Todd Owen's post about using self-balancing trees. The tree obviously does not have to be re-created every time a weight changes. That part just isn't included in the implementation I linked and needs to be added if your weights change a lot.

Answer 3

I like @André Hoffmann's idea of using a binary tree, in which every leaf node corresponds to a question, and every intermediate node stores the sum of the weight of its child nodes. But he says the tree needs to be re-created every time a weight changes.

Actually, this need not be the case! When you change the weight of a given leaf, you only need to update the weights of those nodes between it and the root of the tree. But...you also need some way to find the node within the tree, if you want to modify it.

So my suggestion is to use a self-balancing binary tree (e.g. a red-black tree, AVL tree, etc), which is ordered by the question ID. Operations on the tree need to maintain the property that the weight of any node is equal to the sum of the weights of its children.

With this data structure, the root node's weight W is equal to the sum of the weights of all the questions. You can retrieve a question either by question ID, or by a random weight (between zero and W). This operation, as well as insertions, deletions, or updating the weight of a question are all O(log n).

Answer 4

Have a class which keeps the item:weight pairs (key=item:value=weight) in a hash table.

The class should also maintain a total_weight variable, which is the sum of all the weights in the hash table. The class' methods to add_item, remove_item, and update_weight for an item should keep the total_weight updated. This avoids having to recalculate the total for every choice.

To choose an item: Use a random number such that 1<=random_number<=total_weight. Iterate over the item:weight pairs in the hash table, summing the weights until the random number is <= that running sum. When that happens, the key of the pair you're on is the chosen item.

This is like rolling an imaginary die whose size is the sum of all the weights. For every roll, each item has its own range of numbers on the die, with the size of each range equal to its item's weight. If the roll result falls within an item's range, that item is the chosen one.

Editing to add the following sample code after the request in the comment below. Tested this with Python 2.5.2:

from random import randint  # Import randint function from random module.

class WeightedCollection(object):
    def __init__(self):
        self.total_weight = 0
        self.items = {}  # This is a python dictionary == a hash table
    def add_item(self, item, weight):
        self.items[item] = weight
        self.total_weight += weight
    def remove_item(self, item):
        self.total_weight -= self.items[item]  # Subtracts the weight.
        del(self.items[item])
    def update_weight(self, item, new_weight):
        self.total_weight += (new_weight - self.items[item])
        self.items[item] = new_weight
    def get_random_item(self):
        ''' Returns random selection but weighted by item weights. '''
        # Result of call below is 1 <= random_number <= self.total_weight...
        random_number = randint(1, self.total_weight)
        sum_so_far = 0
        # For every item and its weight...
        for item, weight in self.items.iteritems():
            sum_so_far += weight
            if random_number <= sum_so_far:
                return item

# Usage demo...

questions = WeightedCollection()

questions.add_item('What is your name?', 1)
questions.add_item('What is your favorite color?', 50)
questions.add_item('What is the meaning to life?', 100)

print 'Here is what the dictionary looks like:'
print questions.items
print ''
print "Total weight:", questions.total_weight
print ''
print 'Some sample random picks...'
for i in range(5):
    print questions.get_random_item()

And here is the output:

Here is what the dictionary looks like:
{'What is the meaning to life?': 100, 'What is your name?': 1, 'What is your favorite color?': 50}

Total weight: 151

Some sample random picks...
What is your favorite color?
What is the meaning to life?
What is the meaning to life?
What is your favorite color?
What is the meaning to life?