Python: Select Item from Object List Based on Probability

Question

Possible Duplicate:
Weighted random selection with and without replacement

I have a long object list of items. I want to randomly select an item from the list based on the probability. The list looks like the following:

class Item:
  def __init__(self, pid, hits, qtyPerOrder):
    self.pid = pid
    self.bay = hits
    self.qtyPerOrder = int(qtyPerOrder)

itemList = [('RGSCAF', 181  ,6), ('WAR10227', 54    ,3), ('AD2020WOC', 31   ,4)]

Basically, I want a function that will go through the list, assign probability weights based on hits, then randomly choose n number of objects based on the probability. So in this example, there would be a higher probability that the object ('RGSCAF', 181 ,6) is returned since it has the highest hits value.

Another probable dupe: [How to do weighted random sample of categories in python](http://stackoverflow.com/q/6432499) — Martijn Pieters, Sep 21 '12 at 19:46

DigitalGhost · Answer 1 · 2012-09-21T20:24:26.087

0

Not the fastest solution but it gets the point across:

def getNWeightedRandoms(n):
    retval = []
    for x in xrange(0,n):
        retval.append(weightedRandom())
    return retval

def weightedRandom():
    sum = 0
    for item in itemList:
        sum += item.bay
    i = random.randint(0,sum-1)
    for item in itemList:
        i -= item.bay
        if i<0:
            return item

edited Sep 21 '12 at 20:24

answered Sep 21 '12 at 19:40

DigitalGhost

773
1
5
14

This doesn't return a sample of size `n`, only one item is picked. – Martijn Pieters Sep 21 '12 at 19:41
Added function to call weightedRandom n times. – DigitalGhost Sep 21 '12 at 20:24
That method allows for duplicates, I don't think that's what the OP wants. – Martijn Pieters Sep 21 '12 at 20:25
the getNWeightedRandoms(n) seems to run an infinite loop – user1683885 Sep 21 '12 at 20:41
It's probably just taking a long time because it's O(N*M) where M is the size of the list. You can speed it up by storing the cumulative hits for each item (e.g. item 2 has cumhits equal to 0.hits + 1.hits + 2.hits), then using bisect instead of a for loop in weighedRandom. – DigitalGhost Sep 21 '12 at 21:09

Python: Select Item from Object List Based on Probability

1 Answers1