algorithme pour choisir ensemble des gagnants en utilisant des poids différents

Question

Je tente de concevoir un algorithme qui fait ce qui suit.

Entrée:

J'ai un ensemble de touches (n total) qui sont mis en correspondance avec ensemble de propriétés. Les propriétés contiennent le poids pour chaque propriété et la valeur de la propriété.

Sortie:

Identifier un ensemble de clés qui sont qualifiés (k totale) en fonction de l'ensemble des propriétés et de leurs poids et de valeurs respectives.

En outre, les données doivent être modifiées en tant que tel dans chaque cycle de choisir les gagnants tels que les chances de quelqu'un qui n'a pas été choisi va dans le prochain cycle (alors que les chances de quelqu'un qui a gagné serait comme si elles sont complètement nouveau dans le système).

Si tout va bien la question à l'est claire. En fait, la valeur de la propriété et le poids respectif détermineraient quelles clés sont plus susceptibles de gagner (une valeur plus élevée avec un poids plus élevé augmenterait la probabilité de cette clé gagnante) et nous finissent par se retrouver en choisissant tout le monde.

Toute entrée sur la façon dont cela peut être fait serait grandement apprécié.

Merci! - Azeem

Answer 1

Considérez votre poids sous forme de segments d'une ligne, avec la longueur totale de ligne égale à la somme des poids. Choisir un nombre aléatoire uniforme entre 0 et cette longueur. Le gagnant est le candidat dont le segment le nombre tombe dans.

Supprimer le gagnant, et réduire la longueur totale de la ligne en conséquence. Ensuite, répétez le processus avec les autres candidats jusqu'à ce que vous avez choisi votre k.

Après le cycle, les perdants rééchelonner à occuper la majeure partie de la longueur d'origine et rajoutez les gagnants avec le petit morceau restant divisé à parts égales entre eux.

Answer 2

une méthode efficace mais non optimisée serait de faire une liste de tous les candidats, mais append index supplémentaires pour contestest proportionnelle au poids.

est totalement hors psuedo contexte d'une mise en œuvre réelle, mais vous devriez avoir l'idée.

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;
}