Choosing items from a list on a percent basis

Question

I am trying to make a program using Python that takes names from a list, and displays the names from the list in a random order, while only using each name once. I have gotten that far, and made it work with the following code:

import random

drivers = [
"John Doe",
"Bill Smith",
"Trent Baxter",
"Ray Olson",
]

random.shuffle(drivers)

for position in drivers:
    print(position)

OUPUT:

Bill Smith
John Doe
Ray Olson
Trent Baxter

This works, however I would like to have the program assign values to each name to make them more, or less likely to get picked, while still only choosing each name once.

What do you mean by "picked"? You're just shuffling them, not choosing an item. http://stackoverflow.com/questions/14992521/python-weighted-random may be helpful? — Wooble, Oct 16 '14 at 17:04
might be easier add extra copies of the names you want to come out more often — Padraic Cunningham, Oct 16 '14 at 17:05
See also http://programmers.stackexchange.com/questions/233541/how-to-implement-a-weighted-shuffle — aruisdante, Oct 16 '14 at 17:06
There are a bunch of implementations with performance notes here: http://eli.thegreenplace.net/2010/01/22/weighted-random-generation-in-python — Peter DeGlopper, Oct 16 '14 at 17:15

aruisdante · Answer 1 · 2014-10-16T17:26:17.557

Here's a simple variant that will do what you want. Note that there are almost certainly much more efficient ways to do this, as this is currently O(n^2) in run time and uses n*m maximum memory where n is input population size and m is average weight, as it builds a list that has one copy of the input list value per weight.

import random
import itertools

def random_weighted_shuffle(input_population):
    '''
    :param input_population: {name:weight}, where weight is the 'number of chances' that this particular name will be drawn
    '''
    out_list = []
    while input_population:
        lotto_list = list(itertools.chain.from_iterable([name]*weight for name, weight in input_population.iteritems()))
        selection  = lotto_list[random.randint(0,len(lotto_list)-1)]
        del input_population[selection]
        out_list.append(selection)
    return out_list

A very important note: As written, this method is destructive to the input dictionary.

Usage:

>>> random_weighted_shuffle({'a':10,'b':2,'c':5})
['a', 'b', 'c']
>>> random_weighted_shuffle({'a':10,'b':2,'c':5})
['a', 'c', 'b']
>>> random_weighted_shuffle({'a':10,'b':2,'c':5})
['b', 'c', 'a']
>>> random_weighted_shuffle({'a':10,'b':2,'c':5})
['c', 'a', 'b']
>>> random_weighted_shuffle({'a':10,'b':2,'c':5})
['a', 'c', 'b']

kurtosis · Answer 2 · 2014-10-16T17:42:43.237

Your question can be interpreted different ways. If you mean that the number of picked elements is not fixed, each element has it's own probability to get picked, and all the picking occurs independently, than the task is solved this way (seems like O(n)):

from scipy.stats import bernoulli

probs = [0.2, 0.5, 0.7, 0.1]

for i, d in enumerate(drivers):
    if bernoulli.rvs(probs[i], size=1)[0]:   # generates a list of length 1 containing Bernoulli random variable
        print d

score 0 · Accepted Answer · answered Oct 16 '14 at 18:30

Answer using only standard modules:

from itertools import accumulate
from random import uniform

class ProbItem(object):
    def __init__(self, value, prob):
        self.value = value
        self.prob = prob

def pick(items):
    accum = list(accumulate(item.prob for item in items))
    rand = uniform(0, accum[-1])
    for i, prob in enumerate(accum):
        if rand < prob:
            return items.pop(i).value

drivers = [
    ProbItem("John Doe", 23.7),
    ProbItem("Bill Smith", 17),
    ProbItem("Trent Baxter", 12.43),
    ProbItem("Ray Olson", 9.99),
]

while (drivers):
    print(pick(drivers))

Depending on your necessities, it's better to build a generator...

Choosing items from a list on a percent basis

3 Answers3