Weighted random selection

Hi all, I have a list of objects i want to instantiate from randomly but with a weighted chance, the list can be added to or subtracted from at any time and the weight of each object can be set at anytime. The maximum weight and object can have is 1 and a min of 0. An example of the list might be

object 1, weight = 1
object 2, weight = 1
object 3, weight = 0.2
object 4, weight = 0.4

but the number of objects in the list could change and each of the weights could also change

Any ideas on how this can be achieved.

Thanks

 

have a look at andeeeees random lib which contains a histogram class.

 

Add up the total weight, then pick a random number up to that value. Then loop through the list, accumulating total weight until the total you get is (strictly) larger than the random value picked. When that happens, return the current element.

Example - two items with equal weight, both set to 1. Calculate the total weight (2) and pick a random integer up to that value, so 0 or 1. Suppose you pick 1. You start iterating over the objects - you look at the first object, add its weight (1) to the counter (0), getting a new counter value of 1. It's not strictly larger than the randomly-chosen value (1), so you keep iterating. You process the second object next, adding its weight (1) to the counter (1) getting a new value of 2. That is now larger than the randomly-chosen value (1), so you stop iterating and return the second object.

It doesn't matter whether you use integers or floats, the method works with either.


Another approach that works for reasonably-low integer weight values is to just build an array of result values, putting each result value into the array multiple times according to its weight. Then you just pick a random element from the array.


If the number of objects is very large then neither of these methods are good, but the first can be optimized fairly easily using a preprocess and binary search.