Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Re: implement random selection in Python

Reply
Thread Tools

Re: implement random selection in Python

 
 
J. Clifford Dyer
Guest
Posts: n/a
 
      11-17-2007
On Fri, 2007-11-16 at 16:47 -0800, Bruza wrote:
I think I need to explain on the probability part: the "prob" is a
> relative likelihood that the object will be included in the output
> list. So, in my example input of
>
> items = [('Mary',30), ('John', 10), ('Tom', 45), ('Jane', 15)]
>
> So, for any size of N, 'Tom' (with prob of 45) will be more likely to
> be included in the output list of N distinct member than 'Mary' (prob
> of 30) and much more likely than that of 'John' (with prob of 10).
>
> I know "prob" is not exactly the "probability" in the context of
> returning a multiple member list. But what I want is a way to "favor"
> some member in a selection process.
>

My understanding of what you are looking for is that on each individual selection, the probability of picking a given name is that name's prob value, divided by the sum of all prob values. That is, in the following case:

items = [('Mary',96),('Shimon',1),('Aisha',1),('Toshiro',2)]
N = 3

On the first pass Mary has a 96% chance of getting selected, Shimon a 1% Chance, Aisha a 1% chance and Toshiro a 2% chance.

If Mary gets selected, then on the second round Shimon and Aisha should each have a 25% chance of getting selected, and Toshiro a 50% chance.

If Shimon gets selected, then on round three, Aisha will have a ~33% chance, and Toshiro a little less than 67%.

If that is correct, then the following might meet your needs:

from random import choice

def select(weighted_list, n=1):
selected = set()
for iteration in xrange(n):
print iteration
selection_list = []
for item in weighted_list:
if item[0] not in selected:
selection_list.extend([item[0]] * item[1])
#print selection_list
this_choice = choice(selection_list)
#print this_choice
selected.add(this_choice)
return selected

if __name__ == '__main__':
items = [('Mary',96),('Shimon',1),('Aisha',1),('Toshiro',2)]
N = 3
print select(items, 3)


It creates a new selection list at every pass, but it should be a marked improvement over solutions that have to flail against already chosen values, especially in unbalanced cases like the one I've shown above. I have not run tests to establish this for certain. Exercise left to the reader.

If you care who was chosen first or last (like, say, if this is for selecting members of a kick ball team), you may want to replace the selected set with a list. Or you may want to keep both the set and a list. Depends on your needs.

Cheers,
Cliff

 
Reply With Quote
 
 
 
 
Scott David Daniels
Guest
Posts: n/a
 
      11-20-2007
J. Clifford Dyer wrote:
> My understanding of what you are looking for is that on each individual selection,
> the probability of picking a given name is that name's prob value, divided by the
> sum of all prob values. That is, in the following case:
> items = [('Mary', 96),('Shimon', 1), ('Aisha', 1), ('Toshiro', 2)]
> ... On the first pass Mary has a 96% chance of getting selected, ....
> If that is correct, then the following might meet your needs:
>
> from random import choice
>
> def select(weighted_list, n=1):
> selected = set()
> for iteration in xrange(n):
> print iteration
> selection_list = []
> for item in weighted_list:
> if item[0] not in selected:
> selection_list.extend([item[0]] * item[1])
> #print selection_list
> this_choice = choice(selection_list)
> #print this_choice
> selected.add(this_choice)
> return selected


or even:

def picks(weighted_list, N):
result = []
adict = dict(weighted_list)
total = sum(adict.values())
for i in range(N):
score = random.random() * total
for choice, weight in cp.iteritems():
if weight < score:
score -= weight
else:
result.append(choice)
total -= cp.pop(choice)
break
else:
raise ValueError('ran out of data')
return result

-Scott
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Python 2.7.3 tempfile.py, ln34, from random import Random as _Random dbv Python 4 03-25-2013 12:54 PM
Math.random() and Math.round(Math.random()) and Math.floor(Math.random()*2) VK Javascript 15 05-02-2010 03:43 PM
random.random(), random not defined!? globalrev Python 4 04-20-2008 08:12 AM
implement random selection in Python Bruza Python 18 11-19-2007 01:31 PM
JTable with row selection, but no cell selection Simon Niederberger Java 2 01-07-2005 04:17 PM



Advertisments