6

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?

8
  • 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, 2017 at 17:27
  • Possible duplicate of A weighted version of random.choice Oct 13, 2017 at 17:30
  • Possible duplicate of stackoverflow.com/questions/9330394/…
    – A R
    Oct 13, 2017 at 17:32
  • 2
    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, 2017 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? Oct 13, 2017 at 18:13

3 Answers 3

7

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)

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

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.