Choisir un élément aléatoire de la liste avec probabilité

Question

I Avoir une liste qui contient quatre éléments (A, B, C, D). Chaque article a une probabilité d'être choisi. Disons par exemple que A a 74% de chances d'être choisi, B 15%, C 7% et D 4%.

Je veux créer une fonction qui choisit au hasard un élément en fonction de sa probabilité.

Une aide s'il vous plaît?

Answer 1

Définir une classe pour vos articles comme celui-ci:

class Items<T> 
{ 
    public double Probability { get; set; } 
    public T Item { get; set; } 
} 

initialize il

var initial = new List<Items<string>> 
{ 
    new Items<string> {Probability = 74/100.0, Item = "A"}, 
    new Items<string> {Probability = 15/100.0, Item = "B"}, 
    new Items<string> {Probability = 7/100.0, Item = "C"}, 
    new Items<string> {Probability = 4/100.0, Item = "D"}, 
}; 

alors vous devez le convertir pour agréger une somme des probabilités de 0 à 1

var converted = new List<Items<string>>(initial.Count); 
var sum = 0.0; 
foreach (var item in initial.Take(initial.Count - 1)) 
{ 
    sum += item.Probability; 
    converted.Add(new Items<string> {Probability = sum, Item = item.Item}); 
} 
converted.Add(new Items<string> {Probability = 1.0, Item = initial.Last().Item}); 

maintenant vous pouvez choisir un élément de collection converted par rapport à la probabilité:

var rnd = new Random(); 
while (true) 
{ 
    var probability = rnd.NextDouble(); 
    var selected = converted.SkipWhile(i => i.Probability < probability).First(); 
    Console.WriteLine($"Selected item = {selected.Item}"); 
} 

REMARQUE: ma mise en œuvre ont O(n) complexité. Vous pouvez optimiser avec recherche binaire (parce que les valeurs dans converted collection sont classés)

Answer 2

Votre meilleur pari est de choisir un nombre de 1-100, et voir si elle tombe dans cette catégorie.

code pseudo -

x = randnum(1-100) 
if 1 <= x < 50: 
    #50%, etc. 

Answer 3

using System; 

public class Test{ 
    private static String[] values = {"A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","B","B","B","B","B","B","B","B","B","B","B","B","B","B","B","C","C","C","C","C","C","C","D","D","D","D",}; 

    private static Random PRNG = new Random(); 

    public static void Main(){ 
     Console.WriteLine(values[PRNG.Next(values.Length)]); 
    } 
} 

Answer 4

Mes excuses pour répondre à celui-ci comme ça - je consulte un peu comme une sorte de puzzle « Euler.Net », et une façon de jouer avec les génériques.

Quoi qu'il en soit, voici mon aller à elle:

public class WeightedItem<T> 
{ 
    private T value; 
    private int weight; 
    private int cumulativeSum; 
    private static Random rndInst = new Random(); 

    public WeightedItem(T value, int weight) 
    { 
     this.value = value; 
     this.weight = weight; 
    } 

    public static T Choose(List<WeightedItem<T>> items) 
    { 
     int cumulSum = 0; 
     int cnt = items.Count(); 

     for (int slot = 0; slot < cnt; slot++) 
     { 
      cumulSum += items[slot].weight; 
      items[slot].cumulativeSum = cumulSum; 
     } 

     double divSpot = rndInst.NextDouble() * cumulSum; 
     WeightedItem<T> chosen = items.FirstOrDefault(i => i.cumulativeSum >= divSpot); 
     if (chosen == null) throw new Exception("No item chosen - there seems to be a problem with the probability distribution."); 
     return chosen.value; 
    } 
} 

Utilisation:

 WeightedItem<string> alice = new WeightedItem<string>("alice", 1); 
     WeightedItem<string> bob = new WeightedItem<string>("bob", 1); 
     WeightedItem<string> charlie = new WeightedItem<string>("charlie", 1); 
     WeightedItem<string> diana = new WeightedItem<string>("diana", 4); 
     WeightedItem<string> elaine = new WeightedItem<string>("elaine", 1); 

     List<WeightedItem<string>> myList = new List<WeightedItem<string>> { alice, bob, charlie, diana, elaine }; 
     string chosen = WeightedItem<string>.Choose(myList);