Pick random element from list with probability

Question

I Have a list that contains four item (A, B, C, D). Every item has a probability to be chosen. Let's say for example A has 74% of chance to be picked, B 15%, C 7% ,and D 4%.

I want to create a function that choose randomly an item according to its probability.

Any help please?

Answer 1

Define a class for your items like this:

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

then initialize it

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

then you need to convert it to aggregate a sum of probabilities from 0 to 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});

now you can pick an item from converted collection with respect to probability:

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

NOTE: my implementation have O(n) complexity. You can optimize it with binary search (because values in converted collection are sorted)

Answer 2

My apologies for answering this one like this - I'm kinda viewing it as a sort of "Euler.Net" puzzle, and a way of playing around with Generics.

Anyway, here's my go at it:

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

Usage:

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