I need random algorithm with weighing options in .net

Question

Hello,

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. Any code samples in .net are appreciated, although algorithm description is nice, too. Thanks

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

Answer 1

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

Answer 2

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.