View Full Version : [Python] Randomly select list item with a certain probability

blazemore

February 22nd, 2012, 03:33 PM

I can't seem to get my head round this, although I'm sure it's fairly simple.

I have a list of tuples like this: (c, p) where p is a number between 0 and 1.

I need to return an item from this list, where an item's chance of being selected is equal to p.

So if I had a list like this:

[

(a, 0.1)

(b, 0.5)

(c, 0.5)

]

it could return any of them, but b and c are equally likely, and 5 times more likely than a.

Sorry if I haven't explained this very well.

For context, this is part of a genetic algorithm I am writing.

Bachstelze

February 22nd, 2012, 03:34 PM

Th

blazemore

February 22nd, 2012, 03:44 PM

Th

Thanks, that fixed it.

;)

Bachstelze

February 22nd, 2012, 03:53 PM

firas@av104151 ~ % cat prob.py

import random

l = [('a', 1), ('b', 5), ('c', 5)]

def randitem(l):

# Make the probabilities add up to 1, preserving ratios

s = sum([b for (a,b) in l])

l2 = []

for (a,b) in l:

l2.append((a, b/s))

r = random.random()

for (a,b) in l2:

if r < b:

return a

else:

r -= b

# test

res = {'a':0, 'b':0, 'c':0}

for i in range(10000):

res[randitem(l)] += 1

print('a: %s (%s%%)' % (res['a'], res['a']/100))

print('b: %s (%s%%)' % (res['b'], res['b']/100))

print('c: %s (%s%%)' % (res['c'], res['c']/100))

firas@av104151 ~ % python3 prob.py

a: 895 (8.95%)

b: 4521 (45.21%)

c: 4584 (45.84%)

Bachstelze

February 22nd, 2012, 03:57 PM

Just in case it wasn't clear the first time. ;)

surfer

February 22nd, 2012, 04:03 PM

a different approach; i do not normalize the probabilities to 1 (which would probably be the better idea...). this is not well tested!

#!/usr/bin/python

import random

class RandomChoice(object):

'''

'''

def __init__(self, lst):

'''

lst: the list in the form [ (element, relative_probability) ]

'''

self.lst = lst

self.limits = []

p_sum = 0

for item in lst:

p_sum += item[1]

self.limits.append(p_sum)

print self.limits

self.p_max = p_sum

def _get_index(self, rnd):

'''

Given the radnom number rnd (0<=rnd<p_max), return the list index.

'''

last = 0.0

for (i, p) in enumerate(self.limits):

if last <= rnd < p:

return i

last = p

def get(self):

'''

'''

rnd = random.uniform(0, self.p_max)

i = self._get_index(rnd)

return self.lst[i]

# test:

lst = [

('a', 0.1),

('b', 0.5),

('c', 0.5)

]

rc = RandomChoice(lst)

for i in xrange(100):

print rc.get()

and, yes 'Th' is much more concise!

Powered by vBulletin® Version 4.2.2 Copyright © 2018 vBulletin Solutions, Inc. All rights reserved.