I have a problem in which I have a large list of items sorted by "weights". I need to be able to randomly select items from this list, but the items closer to the start (greater weights) must have a greater chance of being selected based on an "elitism" factor.
I realize that similar questions have been asked before, but the catch here is that this list will be changing over time. New values will be sorted into the list as the last item is deleted (to keep a constant sized pool of "optimized" values).
First off, what would be the most efficient way of doing the selection? Selection must happen in real time from a list anywhere from 50 to 1000 item long.
Second, what would be the best data structure to use here? I'm using C#.
I just thought of a possible solution, but I'd like some feedback on the idea. What if I were to generate a random float value within a certain range, and then do something along the lines of squaring it? Small values would return small values, and large values would return MUCH larger values. From what I can tell, mapping this result to the length of the list should give the desired effect. Does this sound right?
Unfortunately, I can't offer any code right now, but some ideas:
As your list is sorted from high weighted to low weighted, you should be able to use a random number generator based on a normal distribution. If you don't have such a random number generator at hand, you can transform a uniform distribution into a normal distribution using the code found here: Random Gaussian Variables
I'm terrible at explaining, but I'l try: You can define the bias (the mean value) at 0 and the sigma (the deviation) at, let's say, 3. Then you take the absolute value from the generated number, as you may get negative numbers.
This will give you a number generator, that has a high probably around the bias number (0 in the above example), and a lower probability for numbers that deviate much from there.
As I said, I'm terrible at explaining