CODEWITHSUNDEEP
c#.netalgorithmrandom
Tomislav Markovski
Tomislav Markovski

Reputation: 12346

I need random algorithm with weighing options

I have a requirement in my .NET project where I need to select an item from a collection, each item has a Weight (integer from 1 to 10) assigned to it.

I need a random generator that would take this weight into consideration i.e., the higher the weight, the more chances the object would be selected.

Quick copy/paste C# code in case someone stumbles upon this.

    class RandomWeightedSelector<T>
    {
        private List<T> items = new List<T>();

        public void Add(T item, uint weight = 1)
        {
            for (int i = 0; i < weight; i++)
                items.Add(item);
        }

        public T GetRandom()
        {
            return items[new Random().Next(0, items.Count)];
        }
    }

Upvotes: 5

Views: 2002

Answers (3)

Brian MacKay
Brian MacKay

Reputation: 32037

What you're looking for is called the Weighted Selector algorithm. I actually created an open source C# project for this some time ago!

It's very easy to use and efficient. Also, the documentation should get you going with no problem.

Here are a few links:

Upvotes: 1

Michael Madsen
Michael Madsen

Reputation: 55009

Here's an algorithm which doesn't require adding the items multiple times to a list. It can also work with non-integer weights, although if you're using NextDouble from System.Random, you'll have to scale all of the weights to add up to 1, or multiply the value from NextDouble with S to get it in the desired range.

Given a list L of items (I,W), where I is the item and W is the weight:

  1. Add all of the weights together. Call this sum S.
  2. Generate a random number between 0 and S (excluding S, but including 0). Call this value R.
  3. Initialize a variable to 0 to keep track of the running total. We'll call this T.
  4. For each item (I,W) in L:
    1. T=T+W
    2. If T > R, return I.

Upvotes: 9

Forrest Voight
Forrest Voight

Reputation: 2257

Make a list and insert each item in Weight number of times. Then choose a random item from the list.

Upvotes: 4

Related Questions