algorithm to pick set of winners using different weights

Question

I'm attempting to design an algorithm that does the following.

Input:

I've a set of keys (total n) that are mapped to set of properties. The properties contain the weight for each property and the value for the property.

Output:

Identify a set of keys that are qualified (total k) based on the set of properties and their respective weights and values.

Additionally, the data should be modified as such in every cycle of choosing winners such that the chances of someone who was not chosen goes up in the next cycle (whereas the chances of someone who has won would be as if they are completely new in the system).

Hopefully the issue at hand is clear. Basically, the value of the property and the respective weight would determine which keys are more likely to win (a higher value with a higher weight would increase the probability of that key winning) and we will eventually end up choosing everyone.

Any input on how this can be done would be greatly appreciated.

Thanks! - Azeem

Answer 1

Consider your weights as segments of a line, with the overall line length equal to the sum of the weights. Pick a uniform random number between 0 and that length. The winner is the candidate whose segment the number falls into.

Remove that winner, and reduce the overall line length accordingly. Then repeat the process with the remaining candidates until you've chosen your k.

After the cycle, rescale the losers to occupy most of the original length and add back the winners with the remaining small chunk divided evenly between them.

Answer 2

an unoptimized but effective method would to make a list of all contestants, but append additional indexes for contestest proportional to weight.

psuedo is totally out of context of any real implementation, but you should get the idea.

const int DEFAULT_WEIGHT = 1;
public List<Contestant> items = new List<Contestant>();
public List<Guid> LotteryPool = new List<int>();

public Contestant Roll()
{
     Random rnd = new Random();
     rnd.Seed = DateTime.Now.Ticks;

     // Generate LotteryPool
     foreach(Contestant item in items)
     {
              for(int i = 0; i < item.Weight; i++)
              {
                       LotteryPool.Add(item.Id);
              }

              item.Weight++;
     }

     // Find the contestant matching a random id from the pool.
     Contestant result = FindContestant(LotteryPool[rnd.Next(0, LotterPool.Count]);

     // apply the default weight the winner
     result.Weight = DEFAULT_WEIGHT;

     return result;
}