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?

You must give it a try first, and we'll help you with any problems you encounter. SO doesn't write code entirely for you. — Sach, Oct 13 '17 at 17:27
Possible duplicate of [A weighted version of random.choice](https://stackoverflow.com/questions/3679694/a-weighted-version-of-random-choice) — Bill the Lizard, Oct 13 '17 at 17:30
Possible duplicate of https://stackoverflow.com/questions/9330394/how-to-pick-an-item-by-its-probability — A R, Oct 13 '17 at 17:32
Generate random number from 0 to 1. If it is less than A probability (<0.74) - choose A. Otherwise if it is less than A+B probability (< 0.74+0.15) - choose B, and so on. — Evk, Oct 13 '17 at 17:48
@Evk: Suppose there are a large number n of buckets. Can you come up with an algorithm that does not involve making O(n) comparisons? — Eric Lippert, Oct 13 '17 at 18:13
@EricLippert I myself can only come up with binary search in that list of cumulated probabilities (List.BinarySearch will do), but I found this algorithm: https://en.m.wikipedia.org/wiki/Alias_method which (after nlog(n) one-time preparation) can do this in o(1) time. — Evk, Oct 13 '17 at 19:01
What's wrong in choosing something as `random(s.length())` as index for string `s` `"AAAAB"` (or array) where `A` is 80% and `B` is 20% (apart from the assumption that the probability needs to be whole numbers)? So O(1) space and O(1) time. — hIpPy, Oct 13 '17 at 19:11
@hlppy that works but it is not o(1) in time or space if the distribution is unknown at compile time. Its at least linear in both to build the string. — Eric Lippert, Oct 13 '17 at 23:23

Aleks Andreev · Accepted Answer · 2017-10-13T18:03:19.790

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)

score 2 · Answer 2 · answered Oct 13 '17 at 18:57

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

score -2 · Answer 3 · answered Oct 13 '17 at 18:43

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

Pick random element from list with probability

3 Answers3

Linked