Many times I need to choose randomly from a list of 'neighbors' according to some weight assigned to them, and I'd like to share my technique. My language of choice is Python, but this technique should work in any language that has some sort of list and a random number generator (or can access one).

import random
def choose_from_weights(lst):
    total = sum(lst)
    chosen = random.randrange(total)
    it = iter(lst)
    i = 0
    while chosen > 0:
        chosen -= next(it) # next is only in 2.6+, use .__next__ if below 2.6
        i += 1
    return i

choose_from_weights([1,2,4,5,6,7])
# or
choose_from_weights([.1,.2,.3,.4])

Basically, this takes a list of weights and chooses a number between 0 and the sum of those weights. It then finds where that number would land and returns that index.

Here's a diagram of sorts:

|--w0--|-w1-|-w2-|--w3--|---w4---|-w5-|w6|
-------------------------->ch

Here, ch lands inside of w4 so the index returned is 4.

I'm not sure what to call this, as I'm sure it's been run into before and probably has some great mathematician's name or at least some convoluted one, but Google doesn't turn up anything other than a few similar attempts.

I believe mine to be the most universal because others require the actual item to be next to its weight, which can cause problems sometimes. Mine only requests the actual weights as some iterable, so it can be a generator, list, tuple, array, or more. Also, it extends to other languages better since, as a function, it can be statically typed; though templates could be used to make the other methods useful in C++ and its variants.

If you know of the name for this, please let me know in the comments!