Does anyone know of an efficient way of doing a weighted random choice? (I don't even know what algorithms like this would be called.) Preferably, something that doesn't grow exponentially with the number of elements in the list, or the size of their respective values.
For example: Assume I have a list of integer elements. I want to pick an index from that list, using the value of said elements to control the probability of selecting a given index: w = [5, 20, 75] wrand(w) Where wrand() will return '2', (the index of 75), about 75% of the time. It would return '1', (the index of 20) about 20% of the time, and 0, about 5% of the time. It could return the actual value, but returning the index seems more flexible. The implementation doesn't have to work exactly like this, even if the weight values don't add up to 100, or are arbitrary, that's fine. Hopefully you get the idea. Here's what I tried (it works, but is slow): ### Begin Code Example ### import random random.seed(2) #<-- So we can reproduce the sequence for testing. def wrandom(weights): ''' Return a randomly selected index of the 'weights' list, using the values of that list to affect probability of said index being returned. ''' debug = False flattened = [] for i, w in enumerate(weights): if debug: print "i, w: ", i, w for k in range(w): flattened.append(i) if debug: print "flattened: ", flattened rnd = random.randint(0, (len(flattened) - 1)) return flattened[rnd] # Not test it: print wrandom([5, 20, 75]) print wrandom([5, 20, 75]) print wrandom([5, 20, 75]) ### End Code Example ### It works and is easy enough to understand, but when the number of list items gets large, or the weights get heavy, things get ugly. -Modulok- _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor