CODEWITHSUNDEEP
pythonlistrandompython-2.7
user1767774
user1767774

Reputation: 1825

Python - choosing random object from a list

I have list of objects "p", every object has some number "a" (for example p[3].a = 5) . I want to choose random object from the list, in the way that the probability of choosing an object is proportional to its value of a, i.e. the probability of choosing object with a=5 is five times the probability of choosing object with a=1. How can I do it with Python/Pylab/Numpy?

thank you!

Upvotes: 1

Views: 1147

Answers (3)

Matthias
Matthias

Reputation: 13222

I'd suggest using bisect

from bisect import bisect

class Element(object):
    def __init__(self, value):
        self.a = value
    def __repr__(self):
        return 'Element({})'.format(self.a)

data = [Element(3), Element(5), Element(7), Element(1)]
last = 0
breakpoints = []
for element in data:
    breakpoints.append(last + element.a)
    last += element.a
print(breakpoints)

for random_value in xrange(last):
    pos = bisect(breakpoints, random_value)
    print(random_value, data[pos])

You have to build the list with the breakpoints just once. Then you can use it with the pretty fast bisect algorithm as long as you like.

The last loop is just to demonstrate the result.

Edit: An alternative approach to get the breakpoints (I didn't like the for-loop):

values = [value.a for value in data]
breakpoints = [sum(values[:pos+1]) for pos in xrange(len(values))]

Upvotes: 0

FogleBird
FogleBird

Reputation: 76762

Here's a more efficient way to do it.

import random

def weighted_choice(items):
    # check if no items exist
    if not items:
        return None

    # compute total of all weights
    total = sum(item.weight for item in items)

    # select a random point within the total
    selection = random.randint(0, total - 1)

    # find the corresponding item
    count = 0
    for item in items:
        count += item.weight
        if selection < count:
            return item

Upvotes: 2

Antimony
Antimony

Reputation: 39451

This will work for integer counts, though it won't be efficient for large counts.

c = collections.Counter({k:k.a for k in stuff})
random.choice(list(c.elements()))

Upvotes: 2

Related Questions