以概率從列表中選擇隨機元素

Question

我有一個包含四個項目（A，B，C，D）的列表。每個項目都有可能被選中。舉例來說，A有74％的機會被選中，B 15％，C 7％和D 4％。

我想創建一個函數，根據它的概率隨機選擇一個項目。

請幫忙嗎？

Answer 1

定義一個類爲您的項目是這樣的：

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

對其進行初始化

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

，那麼你需要將其轉換爲聚集之和概率從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}); 

現在你可以相對於從converted收藏挑一個項目的概率：

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

注：我的實現有O(n)複雜。您可以使用二進制搜索優化它（因爲在converted集合值進行排序）

Answer 2

最好的辦法是從1-100挑一個數字，看看它是否屬於這個類別。

僞碼 -

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

我的道歉爲回答這個問題一個這樣的 - 我有點看它作爲一種「Euler.Net」拼圖，和一種與泛型兼容的方式。

無論如何，這是我走在它：

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

用法：

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