how to choose element from list based on probabilities?

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

  1. 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
    #1
    1. Advertising

  2. Matthew Wilson

    John Roth Guest

    "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
    #2
    1. Advertising

  3. 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
    #3
  4. 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
    #4
  5. 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
    #5
  6. Matthew Wilson

    Sidharthk Guest

    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
    #6
  7. Matthew Wilson

    Sidharthk Guest

    (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
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Curious probabilities

    , Apr 10, 2006, in forum: C Programming
    Replies:
    3
    Views:
    320
    Nick Keighley
    Apr 11, 2006
  2. Replies:
    23
    Views:
    654
  3. michael75
    Replies:
    0
    Views:
    1,848
    michael75
    Aug 3, 2010
  4. Victor \Zverok\ Shepelev

    Some probabilities fun

    Victor \Zverok\ Shepelev, May 28, 2007, in forum: Ruby
    Replies:
    0
    Views:
    96
    Victor \Zverok\ Shepelev
    May 28, 2007
  5. Howard Kaikow

    Choose code to run based on incoming URL

    Howard Kaikow, Oct 7, 2004, in forum: Javascript
    Replies:
    14
    Views:
    228
    Howard Kaikow
    Oct 9, 2004
Loading...

Share This Page