# how to choose element from list based on probabilities?

Discussion in 'Python' started by Matthew Wilson, Nov 13, 2003.

1. ### Matthew WilsonGuest

I have a list of very simple circle objects:

class Circle:
def __init__(self, x,y,r):
self.center =(x,y)
self.r = r

I want to write a function that accepts a list of circle objects and
then chooses one of the circles and returns that circle. The circles
with the biggest areas should be the most likely to be chosen, but there
should be some randomness.

Subsequent calls to the function should not return the same circle.

Can anyone help me out?

Matthew Wilson, Nov 13, 2003

2. ### John RothGuest

"Matthew Wilson" <> wrote in message
news:...
> I have a list of very simple circle objects:
>
> class Circle:
> def __init__(self, x,y,r):
> self.center =(x,y)
> self.r = r
>
> I want to write a function that accepts a list of circle objects and
> then chooses one of the circles and returns that circle. The circles
> with the biggest areas should be the most likely to be chosen, but there
> should be some randomness.
>
> Subsequent calls to the function should not return the same circle.
>
> Can anyone help me out?

Look at module "random". I'd suggest sorting in size order
and then applying some variety of bias function, and then removing
the selected item from the list.

John Roth

John Roth, Nov 13, 2003

3. ### Jegenye 2001 BtGuest

Is this a school homework?

0/ add a method to your class Circle which computes the area
1/ make the list (list comprehension!) with tuples of the form
(circleobject, circleobject.area() )
2/ normalize the values to one, i.e. change the the list elements into a
form like (circleobject, circleobject.area()/S) ,
where S is the sum of the areas of all the circles
3/ sort the elements according to the normalized value so that they are in
increasing order
3/ roll a uniform number between 0 and 1 with using the random module
4/ find which element is the first one in the sequence where the normalized
value is already greater than (or equal to) this random value

Use a seed taken from, say, the current time for the random number generator
so that the subsequent calls are randomized.

Best,
Miklós

> I want to write a function that accepts a list of circle objects and
> then chooses one of the circles and returns that circle. The circles
> with the biggest areas should be the most likely to be chosen, but there
> should be some randomness.
>
> Subsequent calls to the function should not return the same circle.
>
> Can anyone help me out?

Jegenye 2001 Bt, Nov 13, 2003
4. ### Jegenye 2001 BtGuest

Well, giving it a second thought, it's perhaps better to build up a list of
the cumulative sums of the normalized areas
,instead of sorting according to the normalized area, and then do the
comparison against that.
[narea1, narea1+narea2, narea1+narea2+narea3, ....]

Miklós

Jegenye 2001 Bt <> wrote in message
news:bp10k7\$k32\$...
> Is this a school homework?
>
> 0/ add a method to your class Circle which computes the area
> 1/ make the list (list comprehension!) with tuples of the form
> (circleobject, circleobject.area() )
> 2/ normalize the values to one, i.e. change the the list elements into a
> form like (circleobject, circleobject.area()/S) ,
> where S is the sum of the areas of all the circles
> 3/ sort the elements according to the normalized value so that they are in
> increasing order
> 4/ roll a uniform number between 0 and 1 with using the random module
> 5/ find which element is the first one in the sequence where the

normalized
> value is already greater than (or equal to) this random value
>
> Use a seed taken from, say, the current time for the random number

generator
> so that the subsequent calls are randomized.
>
> Best,
> Miklós
>
>
>

Jegenye 2001 Bt, Nov 14, 2003
5. ### Anton VredegoorGuest

Matthew Wilson <> wrote:

>I have a list of very simple circle objects:
>
>class Circle:
> def __init__(self, x,y,r):
> self.center =(x,y)
> self.r = r
>
>I want to write a function that accepts a list of circle objects and
>then chooses one of the circles and returns that circle. The circles
>with the biggest areas should be the most likely to be chosen, but there
>should be some randomness.
>
>Subsequent calls to the function should not return the same circle.

Thanks for sharing this problem Below is some not very well tested
code, maybe someone can get at a sample in a more interesting way.
Generating a set of *non-overlapping* circles of different sizes
fitting inside a rectangle may be the next problem?

Anton

from math import pi
from random import uniform

class Circle:
def __init__(self, x,y,r):
self.center = (x,y)
self.r = r

def getarea(self): return pi*self.r**2
area = property(getarea)

def randomcircleindex(circles):
"""area based choice"""
total = 0
treshold = uniform(0,sum([c.area for c in circles]))
for i,c in enumerate(circles) :
total += c.area
if total >= treshold: return i

def gencircles(maxc,maxr):
"""generate random circles with radius <= maxr,
fitting in a square ((0,0),(maxc,maxc)) """
while 1:
x = uniform(maxr,maxc-maxr)
y = uniform(maxr,maxc-maxr)
r = uniform(0,maxr)
yield Circle(x,y,r)

def samplecircles(circles,k):
"""area based sample"""
result = []
n = len(circles)
if k > n :
raise ValueError, 'sample larger than population'
L = circles[:]
for i in xrange(k):
j = randomcircleindex(L)
result.append( L.pop(j))
return result

def pprintcircle(c):
print "(%7.2f,%7.2f)" %c.center,
print "%7.2f %15.2f" %(c.r,c.area)

def test():
nc,maxr,maxc = 10,100,1000
g = gencircles(maxc,maxr)
circles = [g.next() for i in xrange(nc)]
#for c in circles: pprintcircle(c)
#print
selected = samplecircles(circles,10)
for c in selected: pprintcircle(c)

if __name__=='__main__':
test()

Anton Vredegoor, Nov 14, 2003
6. ### SidharthkGuest

Matthew Wilson <> wrote in message news:<>...
> I have a list of very simple circle objects:
>
> class Circle:
> def __init__(self, x,y,r):
> self.center =(x,y)
> self.r = r
>
> I want to write a function that accepts a list of circle objects and
> then chooses one of the circles and returns that circle. The circles
> with the biggest areas should be the most likely to be chosen, but there
> should be some randomness.
>
> Subsequent calls to the function should not return the same circle.
>
> Can anyone help me out?

import random
import math
def getCircleMaker(circleList):
circleList = list(circleList)
circleList.sort(lambda a, b: cmp(b.r, a,r))
def workerFunc():
pos = int(random.randrange(len(circleList)**2)**0.5)
return circleList.pop(pos)
return workerFunc

circlelist = [Circle(0,0,random.randrange(100)) for e in range(100)]

getCircle = getCircleMaker(circlelist)

and now just call getCircle() to get a circle

This is a very simple solution. getCircle will raise an IndexError
when the list finishes.
I havent really tried this but it should work in principle.

Sidharthk, Nov 15, 2003
7. ### SidharthkGuest

(Sidharthk) wrote in message news:<>...
> import random
> import math
> def getCircleMaker(circleList):
> circleList = list(circleList)
> circleList.sort(lambda a, b: cmp(b.r, a,r))
> def workerFunc():
> pos = int(random.randrange(len(circleList)**2)**0.5)
> return circleList.pop(pos)
> return workerFunc
>
>
>

My earlier example wont work. It orders the list incorrectly so you
are more likely to end up with a smaller circle.
here's a corrected example.
class Circle:
def __init__(self, x,y,r):
self.center =(x,y)
self.r = r

import random
def getCircleMaker(circleList):
circleList = list(circleList)
circleList.sort(lambda a, b: cmp(a.r, b.r))
pow = 4
def workerFunc():
pos = int(random.randrange(len(circleList)**pow)**(1.0/pow))
return circleList.pop(pos)
return workerFunc

circlelist = [Circle(0,0,random.randrange(100)) for e in range(100)]

getCircle = getCircleMaker(circlelist)

Changing the value of pow will affect the probability of getting a
larger circle. The larger the value of pow the higher the chance.

Sidharthk, Nov 16, 2003