how to choose element from list based on probabilities?

[Matthew Wilson]

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?

 

[John Roth]

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

 

[Jegenye 2001 Bt]

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

 

[Jegenye 2001 Bt]

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

 

[Anton Vredegoor]

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()

 

[Sidharthk]

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]

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.