Weighted choice

test_weighted_choice.py

if __name__ == '__main__':
    print 'weighted_choice test'

	picked_items = []
	weights = {'1st': 50, '2nd': 30, '3rd': 15, '4th': 5, '5th': 0}

	for i in xrange(100000):
		picked_items.append(weighted_choice(weights))

	for code in sorted(set(picked_items[:])):
		weight_percentage = 1.0 * weights[code] / sum(weights.values())
		picked_percentage = 1.0 * picked_items.count(code) / len(picked_items)
		sign = cmp(weight_percentage, picked_percentage)
		print '{:>4} : {:6.2%} {} {:6.2%} ({:5.2f})'.format(
			code,
			weight_percentage,
			'=' if sign == 0 else '<' if sign < 0 else '>',
			picked_percentage,
			(weight_percentage - picked_percentage) * 100
		)

# Result:
#  1st : 50.00% > 49.54% ( 0.46)
# 2nd : 30.00% < 30.30% (-0.30)
# 3rd : 15.00% < 15.12% (-0.12)
# 4th :  5.00% <  5.04% (-0.04)

weighted_choice.py

def weighted_choice(probabilities):
	'''
	probabilities : {key1: int(probability1), key2: int(probability2)}
	'''
	probs = probabilities.copy()
	roll = random.randrange(1, sum(probs.values()))

	for k in probs.keys():
		v = probs.pop(k)
		s = sum(probs.values())
		if s < roll <= v + s:
			return k

	return random.choice(probabilities.keys())[0]