Probabilistically pick a candidate I have a list of candidates which looks like this:

candidates = [
    {
        'name': 'John',
        'rank': 13
    },
    {
        'name': 'Joe',
        'rank': 8
    },
    {
        'name': 'Averell',
        'rank': 5
    },
    {
        'name': 'William',
        'rank': 2
    }
]


What I want to do is semi-randomly pick one of these candidates, based on its squared rank. So that a candidate A having a rank twice as big as B, will have 4 times more chances to be picked than B.

Here is a naive implementation of the idea I had to solve this problem:

def pick_candidate(candidates):
    # initiates a global probability space
    prob_space = []

    # bring the max rank to 20
    # to avoid useless CPU burning
    # while keeping a good granularity -
    # basically, just bring the top rank to 20
    # and the rest will be divided proportionally
    rate = candidates[0]['rank'] / 20

    # fills the probability space with the indexes
    # of 'candidates', so that prob_space looks like:
    # [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1]
    # if candidates[0] has rank 3 and candidates[1] has rank 2
    for i, c in enumerate(candidates):
        rank = c['rank'] / rate
        for j in range(int(rank*rank)):
            prob_space.append(i)

    # picks a random index from the probability space
    picked_prob_space_index = random.randint(0, len(prob_space)-1)

    # retrieves the matching candidate
    picked_candidate_index = prob_space[picked_prob_space_index]

    return candidates[picked_candidate_index]


The questions I'm thinking of, concerning the above code, are:


Concept: Is the core principle of the algorithm (the idea of building prob_space, etc) overkill and solvable more easily in other ways or with builtins
Implementation: This core principle put aside, what do you think of the implementation? Would you think of a better, cleaner way to write it?
Concept


imho you don't need build prob_space or normalize by max rank == 20
you only need

John: 1 ... 13^2
Joe:  13^2+1 ... 13^2+8^2
Averell: 13^2+8^2+1 ... 13^2+8^2+5^2
William: 13^2+8^2+5^2 ... 13^2+8^2+5^2+2^2
and choice a man having ranint(1, 13^2+8^2+5^2+2^2)

transform list [13**2, 8**2, 5**2, ...] to [13**2, 13**2+8**2, 13**2+8**2+5**2, ...] we can by accumulate
searching in this sorted list [13**2, 13**2+8**2, 13**2+8**2+5**2, ...] we can by binary search algorithm implemented in bisect module
the algorithm:

from collections import namedtuple
from itertools import accumulate
from random import randint
from bisect import bisect_left

Candidate = namedtuple('Candidate', 'name rank')


def pick_random_candidate(candidates):
    assert (len(candidates) &gt; 0) # note: probably we want return None with empty list?
    squared_ranks_accumulated = list(accumulate(c.rank ** 2 for c in candidates))
    random_pick = randint(1, squared_ranks_accumulated[-1])
    return candidates[bisect_left(squared_ranks_accumulated, random_pick)]


if __name__ == "__main__":
    candidates = [Candidate(*t) for t in [('John', 13), ('Joe', 8), ('Averell', 5), ('William', 2)]]
    random_candidate = pick_random_candidate(candidates)
    print(random_candidate)



Implementation


better use from random import randint instead of import random
if you have randint(0, x - 1) you can replace it by randrange(x)
constants like 20 should be defined as variable, e.g. top_rank = 20 or even def pick_candidate(candidates, top_rank=20). Reason: if someone change 20 to 21 in next three months there are high probability that don't change comment (so better when comment explains top_rank not 20)
you can often define structure Candidate as namedtuple (dict is better only sometimes if have some dynamic fields to store)
what's with the empty list of candidates (exception KeyError is expected or something else should be?)