(Python) algorithm to randomly select a key based on proportionality/weight
Question: I'm a bit at a loss as to how to find a clean algorithm for doing the
following:

Suppose I have a dict k:

    
    
    >>> k = {'A': 68, 'B': 62, 'C': 47, 'D': 16, 'E': 81}
    

I now want to randomly select one of these keys, based on the 'weight' they
have in the total (i.e. sum) amount of keys.

    
    
    >>> sum(k.values()) 
    >>> 274
    

So that there's a

    
    
    >>> 68.0/274.0
    >>> 0.24817518248175183
    

24.81% percent change that A is selected.

How would you write an algorithm that takes care of this? In other words, that
makes sure that on 10.000 random picks, A will be selected 2.481 times?


Answer: This should do the trick:

    
    
    >>> k = {'A': 68, 'B': 62, 'C': 47, 'D': 16, 'E': 81}
    >>> import random
    >>> def weighted_pick(dic):
    ...     total = sum(dic.itervalues())
    ...     pick = random.randint(0, total-1)
    ...     tmp = 0
    ...     for key, weight in dic.iteritems():
    ...         tmp += weight
    ...         if pick < tmp:
    ...             return key
    

