473,326 Members | 2,173 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

how to choose element from list based on probabilities?

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?
Jul 18 '05 #1
7 3619

"Matthew Wilson" <mw*****@sarcastic-horse.com> wrote in message
news:sl********************@overlook.homelinux.net ...
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
Jul 18 '05 #2
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?

Jul 18 '05 #3
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 <je*********@fw.hu> wrote in message
news:bp**********@namru.matavnet.hu...
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


Jul 18 '05 #4
Matthew Wilson <mw*****@sarcastic-horse.com> 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()

Jul 18 '05 #5
Matthew Wilson <mw*****@sarcastic-horse.com> wrote in message news:<sl********************@overlook.homelinux.ne t>...
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. :-)
Jul 18 '05 #6
si*******@hotmail.com (Sidharthk) wrote in message news:<8d**************************@posting.google. com>...
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.
Jul 18 '05 #7
In article <sl********************@overlook.homelinux.net>,
Matthew Wilson <mw*****@sarcastic-horse.com> 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.


Given a list of objects and probability weights:

things = [(o1,p1), (o2,p2), (o3,p3), (o4,p4), (o5,p5)]

accum = 0
for o, p in things:
accum += p
if accum * random.random() < p:
selected = o
At the end the probability of any one of the things being
selected is equal to that things probablity weight divided
by the sum of all the weights.

The way to meet the non-duplication requirement is to
remove the object from the working list when it's selected.
Keep track of each candiates index through the selection loop
if you need to.

Regards. Mel.
Jul 18 '05 #8

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

18
by: pmatos | last post by:
Hi, If I have set<unsigned int> s; will *(s.begin()) give me the minimum element of the set? If not, how can I retrieve it? Cheers, Paulo Matos
4
by: Rithish | last post by:
Is there a way to obtain the height of a <SELECT> element dynamically, i.e. through javascript? I want to dynamically display a list box onFocus of a text box element. Also, if the list box...
6
by: lucy | last post by:
Hello comp.lang.js.I need a script to rotate a background image on each newpage load, given the id of the element and a list (array?)of 2 or more image paths ("img1.jpg", "img2.jpg", ...).Actually,...
13
by: bob | last post by:
Let's say you want to iterate through all of the possible combinations that occur when you choose 7 cards from a fifty two card deck. Anyone know the best way to do this? Thanks.
38
by: ssg31415926 | last post by:
I need to compare two string arrays defined as string such that the two arrays are equal if the contents of the two are the same, where order doesn't matter and every element must be unique. ...
8
by: zulander | last post by:
is there a way to find out if the element exist ? dim myarray() as string dim mytxt as string mytxt ="Superman1,Superman2,Superman3,Superman4" myarray=mytxt.split(",") ...
15
by: caca | last post by:
Hello, This is a question for the best method (in terms of performance only) to choose a random element from a list among those that satisfy a certain property. This is the setting: I need to...
1
by: IZZI | last post by:
I've read a materialabout Quicksort algorithsm, it said an approach for choosing a pivot element that is better than "use the entry at location " is that we carry the average of the first and the...
1
Banfa
by: Banfa | last post by:
So the basic sequenced C++ containers are vector - holds data in a contiguous memory block that has the same memory footprint as a classical array. Expensive to insert or delete at the front or...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shćllîpôpď 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.