Selecting item from set given distribution

Question

I have a set of X items such as {blower, mower, stove} and each item has a certain percentage of times it should be selected from the overall set {blower=25%,mower=25%,stove=75%} along with a certain distribution that these items should follow (blower should be selected more at the beginning of selection and stove more at the end). We are given a number of objects to be overall selected (ie 100) and a overall time to do this in (say 100 seconds).

I was thinking of using a roulette wheel algorithm where the weights on the wheel are affected by the current distribution as a function of the elapsed time (and the allowed duration) so that simple functions could be used to determine the weight. Are there any common approaches to problems like this that anyone is aware of?

Currently i have programmed something similar to this in java using functions such as x^2 (with correct normalization for the weights) to ensure that a good distribution occurs. Other suggestions or common practices would be welcome :-)

Answer 1

Your problem description isn't fully clear to me, but I'll try to answer what I understand. First of all, you can select a random item from a weighted distribution by doing the following:

1. Find the sum of the weights of all potential objects which we'll call wsum.
2. Pick a random number, a.
3. Initialize a cumulative variable, total to 0.0.
4. Starting with the first possible object (weight > 0.0), add the weight to total.
5. If a < total/wsum, this number is chosen and we remove it from the list of possible objects as well as subtracting its weight from wsum.
6. If we have chosen enough objects, continue, otherwise go to step 2.

It helps to have the objects sorted by the weights in descending order to improve the speed of the operation a little bit.

That is just to find which object we're choosing from the current distribution. It sounds like your distribution is changing with time so you would just need to change the list of possible objects to be chosen with time.