<p>Consider the class below that represents a Broker:</p>

<pre><code>public class Broker
{
    public string Name = string.Empty;
    public int Weight = 0;

    public Broker(string n, int w)
    {
        this.Name = n;
        this.Weight = w;
    }
}
</code></pre>

<p>I'd like to randomly select a Broker from an array, taking into account their weights.</p>

<p>What do you think of the code below?</p>

<pre><code>class Program
    {
        private static Random _rnd = new Random();

        public static Broker GetBroker(List&lt;Broker&gt; brokers, int totalWeight)
        {
            // totalWeight is the sum of all brokers' weight

            int randomNumber = _rnd.Next(0, totalWeight);

            Broker selectedBroker = null;
            foreach (Broker broker in brokers)
            {
                if (randomNumber &lt;= broker.Weight)
                {
                    selectedBroker = broker;
                    break;
                }

                randomNumber = randomNumber - broker.Weight;
            }

            return selectedBroker;
        }


        static void Main(string[] args)
        {
            List&lt;Broker&gt; brokers = new List&lt;Broker&gt;();
            brokers.Add(new Broker("A", 10));
            brokers.Add(new Broker("B", 20));
            brokers.Add(new Broker("C", 20));
            brokers.Add(new Broker("D", 10));

            // total the weigth
            int totalWeight = 0;
            foreach (Broker broker in brokers)
            {
                totalWeight += broker.Weight;
            }

            while (true)
            {
                Dictionary&lt;string, int&gt; result = new Dictionary&lt;string, int&gt;();

                Broker selectedBroker = null;

                for (int i = 0; i &lt; 1000; i++)
                {
                    selectedBroker = GetBroker(brokers, totalWeight);
                    if (selectedBroker != null)
                    {
                        if (result.ContainsKey(selectedBroker.Name))
                        {
                            result[selectedBroker.Name] = result[selectedBroker.Name] + 1;
                        }
                        else
                        {
                            result.Add(selectedBroker.Name, 1);
                        }
                    }
                }


                Console.WriteLine("A\t\t" + result["A"]);
                Console.WriteLine("B\t\t" + result["B"]);
                Console.WriteLine("C\t\t" + result["C"]);
                Console.WriteLine("D\t\t" + result["D"]);

                result.Clear();
                Console.WriteLine();
                Console.ReadLine();
            }
        }
    }
</code></pre>

<p>I'm not so confident. When I run this, Broker A always gets more hits than Broker D, and they have the same weight.</p>

<p>Is there a more accurate algorithm?</p>

<p>Thanks!</p>

[{'answer_id': 56735, 'author': 'Konrad Rudolph', 'author_id': 1968, 'author_profile': 'https://Stackoverflow.com/users/1968', 'pm_score': 6, 'selected': True, 'text': '<p>Your algorithm is nearly correct. However, the test should be <code>&lt;</code> instead of <code>&lt;=</code>:</p>\n\n<pre><code>if (randomNumber &lt; broker.Weight)\n</code></pre>\n\n<p>This is because 0 is inclusive in the random number while <code>totalWeight</code> is exclusive. In other words, a broker with weight 0 would still have a small chance of being selected –\xa0not at all what you want. This accounts for broker A having more hits than broker D.</p>\n\n<p>Other than that, your algorithm is fine and in fact the canonical way of solving this problem.</p>\n'}, {'answer_id': 57508, 'author': '1800 INFORMATION', 'author_id': 3146, 'author_profile': 'https://Stackoverflow.com/users/3146', 'pm_score': 2, 'selected': False, 'text': '<p>An alternative method favours speed when selecting the broker over memory usage. Basically we create the list containing the same number of references to a broker instance as the specified weight.</p>\n\n<pre><code>List&lt;Broker&gt; brokers = new List&lt;Broker&gt;();\nfor (int i=0; i&lt;10; i++)\n    brokers.Add(new Broker("A", 10));\nfor (int i=0; i&lt;20; i++)\n    brokers.Add(new Broker("B", 20));\nfor (int i=0; i&lt;20; i++)\n    brokers.Add(new Broker("C", 20));\nfor (int i=0; i&lt;10; i++)\n    brokers.Add(new Broker("D", 10));\n</code></pre>\n\n<p>Then, to select a randomly weighted instance is an O(1) operation:</p>\n\n<pre><code>int randomNumber = _rnd.Next(0, brokers.length);\nselectedBroker = brokers[randomNumber];\n</code></pre>\n'}, {'answer_id': 58113, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 1, 'selected': False, 'text': "<p>If you want more speed you can either consider weighted reservoir sampling where you don't have to find the total weight ahead of time (but you sample more often from the random number generator). The code might look something like</p>\n\n<pre><code>Broker selected = null;\nint s = 0;\nforeach(Broker broker in brokers) {\n    s += broker.Weight;\n    if (broker.Weight &lt;= _rnd.Next(0,s)) {\n        selected = broker;\n    }\n}\n</code></pre>\n\n<p>This requires going once through the list brokers. However if the list of brokers is fixed or doesn't change that often you can keep an array of cumulative sums, i.e. A[i] is the sum of weights of all brokers 0,..,i-1. Then A[n] is the total weight and if you pick a number between 1 and A[n-1], say x you find the broker j s.t. A[j-1] &lt;= x &lt; A[j]. For convenience you let A[0] = 0. You can find this broker number j in log(n) steps using binary search, I'll leave the code as an easy exercise. If your data changes frequently this might not be a good way to go since every time some weight changes you might need to update a large portion of the array.</p>\n"}, {'answer_id': 3899874, 'author': 'Cagatay', 'author_id': 425885, 'author_profile': 'https://Stackoverflow.com/users/425885', 'pm_score': 4, 'selected': False, 'text': '<pre><code>class Program\n{\n    static void Main(string[] args)\n    {\n        var books = new List&lt;Book&gt; {\n        new Book{Isbn=1,Name="A",Weight=1},\n        new Book{Isbn=2,Name="B",Weight=100},\n        new Book{Isbn=3,Name="C",Weight=1000},\n        new Book{Isbn=4,Name="D",Weight=10000},\n        new Book{Isbn=5,Name="E",Weight=100000}};\n\n        Book randomlySelectedBook = WeightedRandomization.Choose(books);\n    }\n}\n\npublic static class WeightedRandomization\n{\n    public static T Choose&lt;T&gt;(List&lt;T&gt; list) where T : IWeighted\n    {\n        if (list.Count == 0)\n        {\n            return default(T);\n        }\n\n        int totalweight = list.Sum(c =&gt; c.Weight);\n        Random rand = new Random();\n        int choice = rand.Next(totalweight);\n        int sum = 0;\n\n        foreach (var obj in list)\n        {\n            for (int i = sum; i &lt; obj.Weight + sum; i++)\n            {\n                if (i &gt;= choice)\n                {\n                    return obj;\n                }\n            }\n            sum += obj.Weight;\n        }\n\n        return list.First();\n    }\n}\n\npublic interface IWeighted\n{\n    int Weight { get; set; }\n}\n\npublic class Book : IWeighted\n{\n    public int Isbn { get; set; }\n    public string Name { get; set; }\n    public int Weight { get; set; }\n}\n</code></pre>\n'}, {'answer_id': 8720099, 'author': 'Jordan', 'author_id': 443602, 'author_profile': 'https://Stackoverflow.com/users/443602', 'pm_score': 0, 'selected': False, 'text': '<p>I\'ve come up with a generic version of this solution:</p>\n\n<pre><code>public static class WeightedEx\n{\n    /// &lt;summary&gt;\n    /// Select an item from the given sequence according to their respective weights.\n    /// &lt;/summary&gt;\n    /// &lt;typeparam name="TItem"&gt;Type of item item in the given sequence.&lt;/typeparam&gt;\n    /// &lt;param name="a_source"&gt;Given sequence of weighted items.&lt;/param&gt;\n    /// &lt;returns&gt;Randomly picked item.&lt;/returns&gt;\n    public static TItem PickWeighted&lt;TItem&gt;(this IEnumerable&lt;TItem&gt; a_source)\n        where TItem : IWeighted\n    {\n        if (!a_source.Any())\n            return default(TItem);\n\n        var source= a_source.OrderBy(i =&gt; i.Weight);\n\n        double dTotalWeight = source.Sum(i =&gt; i.Weight);\n\n        Random rand = new Random();\n\n        while (true)\n        {\n            double dRandom = rand.NextDouble() * dTotalWeight;\n\n            foreach (var item in source)\n            {\n                if (dRandom &lt; item.Weight)\n                    return item;\n\n                dRandom -= item.Weight;\n            }\n        }\n    }\n}\n\n/// &lt;summary&gt;\n/// IWeighted: Implementation of an item that is weighted.\n/// &lt;/summary&gt;\npublic interface IWeighted\n{\n    double Weight { get; }\n}\n</code></pre>\n'}, {'answer_id': 11930875, 'author': 'necrogt4', 'author_id': 1594818, 'author_profile': 'https://Stackoverflow.com/users/1594818', 'pm_score': 5, 'selected': False, 'text': "<p>How about something a little more generic, that can be used for any data type?</p>\n<pre><code>using System;\nusing System.Linq;\nusing System.Collections;\nusing System.Collections.Generic;\n\npublic static class IEnumerableExtensions {\n    \n    public static T RandomElementByWeight&lt;T&gt;(this IEnumerable&lt;T&gt; sequence, Func&lt;T, float&gt; weightSelector) {\n        float totalWeight = sequence.Sum(weightSelector);\n        // The weight we are after...\n        float itemWeightIndex =  (float)new Random().NextDouble() * totalWeight;\n        float currentWeightIndex = 0;\n\n        foreach(var item in from weightedItem in sequence select new { Value = weightedItem, Weight = weightSelector(weightedItem) }) {\n            currentWeightIndex += item.Weight;\n            \n            // If we've hit or passed the weight we are after for this item then it's the one we want....\n            if(currentWeightIndex &gt;= itemWeightIndex)\n                return item.Value;\n            \n        }\n        \n        return default(T);\n        \n    }\n    \n}\n</code></pre>\n<p>Simply call by</p>\n<pre><code>    Dictionary&lt;string, float&gt; foo = new Dictionary&lt;string, float&gt;();\n    foo.Add(&quot;Item 25% 1&quot;, 0.5f);\n    foo.Add(&quot;Item 25% 2&quot;, 0.5f);\n    foo.Add(&quot;Item 50%&quot;, 1f);\n    \n    for(int i = 0; i &lt; 10; i++)\n        Console.WriteLine(this, &quot;Item Chosen {0}&quot;, foo.RandomElementByWeight(e =&gt; e.Value));\n</code></pre>\n"}, {'answer_id': 30948171, 'author': 'BlueRaja - Danny Pflughoeft', 'author_id': 238419, 'author_profile': 'https://Stackoverflow.com/users/238419', 'pm_score': 3, 'selected': False, 'text': '<p>Since this is the top result on Google:</p>\n\n<p>I\'ve created <a href="https://github.com/BlueRaja/Weighted-Item-Randomizer-for-C-Sharp" rel="noreferrer">a C# library for randomly selected weighted items</a>.</p>\n\n<ul>\n<li>It implements both the tree-selection and walker alias method algorithms, to give the best performance for all use-cases.</li>\n<li>It is unit-tested and optimized.</li>\n<li>It has LINQ support.</li>\n<li>It\'s free and open-source, licensed under the MIT license.</li>\n</ul>\n\n<p>Some example code:</p>\n\n<pre><code>IWeightedRandomizer&lt;string&gt; randomizer = new DynamicWeightedRandomizer&lt;string&gt;();\nrandomizer["Joe"] = 1;\nrandomizer["Ryan"] = 2;\nrandomizer["Jason"] = 2;\n\nstring name1 = randomizer.RandomWithReplacement();\n//name1 has a 20% chance of being "Joe", 40% of "Ryan", 40% of "Jason"\n\nstring name2 = randomizer.RandomWithRemoval();\n//Same as above, except whichever one was chosen has been removed from the list.\n</code></pre>\n'}, {'answer_id': 37174530, 'author': 'Lord of the Goo', 'author_id': 277389, 'author_profile': 'https://Stackoverflow.com/users/277389', 'pm_score': 0, 'selected': False, 'text': '<p>Just to share my own implementation. Hope you\'ll find it useful.</p>\n\n<pre><code>    // Author: Giovanni Costagliola &lt;giovanni.costagliola@gmail.com&gt;\n\n    using System;\n    using System.Collections.Generic;\n    using System.Linq;\n\n    namespace Utils\n    {\n    /// &lt;summary&gt;\n    /// Represent a Weighted Item.\n    /// &lt;/summary&gt;\n    public interface IWeighted\n    {\n        /// &lt;summary&gt;\n        /// A positive weight. It\'s up to the implementer ensure this requirement\n        /// &lt;/summary&gt;\n        int Weight { get; }\n    }\n\n    /// &lt;summary&gt;\n    /// Pick up an element reflecting its weight.\n    /// &lt;/summary&gt;\n    /// &lt;typeparam name="T"&gt;&lt;/typeparam&gt;\n    public class RandomWeightedPicker&lt;T&gt; where T:IWeighted\n    {\n        private readonly IEnumerable&lt;T&gt; items;\n        private readonly int totalWeight;\n        private Random random = new Random();\n\n        /// &lt;summary&gt;\n        /// Initiliaze the structure. O(1) or O(n) depending by the options, default O(n).\n        /// &lt;/summary&gt;\n        /// &lt;param name="items"&gt;The items&lt;/param&gt;\n        /// &lt;param name="checkWeights"&gt;If &lt;c&gt;true&lt;/c&gt; will check that the weights are positive. O(N)&lt;/param&gt;\n        /// &lt;param name="shallowCopy"&gt;If &lt;c&gt;true&lt;/c&gt; will copy the original collection structure (not the items). Keep in mind that items lifecycle is impacted.&lt;/param&gt;\n        public RandomWeightedPicker(IEnumerable&lt;T&gt; items, bool checkWeights = true, bool shallowCopy = true)\n        {\n            if (items == null) throw new ArgumentNullException("items");\n            if (!items.Any()) throw new ArgumentException("items cannot be empty");\n            if (shallowCopy)\n                this.items = new List&lt;T&gt;(items);\n            else\n                this.items = items;\n            if (checkWeights &amp;&amp; this.items.Any(i =&gt; i.Weight &lt;= 0))\n            {\n                throw new ArgumentException("There exists some items with a non positive weight");\n            }\n            totalWeight = this.items.Sum(i =&gt; i.Weight);\n        }\n        /// &lt;summary&gt;\n        /// Pick a random item based on its chance. O(n)\n        /// &lt;/summary&gt;\n        /// &lt;param name="defaultValue"&gt;The value returned in case the element has not been found&lt;/param&gt;\n        /// &lt;returns&gt;&lt;/returns&gt;\n        public T PickAnItem()\n        {\n            int rnd = random.Next(totalWeight);\n            return items.First(i =&gt; (rnd -= i.Weight) &lt; 0);\n        }\n\n        /// &lt;summary&gt;\n        /// Resets the internal random generator. O(1)\n        /// &lt;/summary&gt;\n        /// &lt;param name="seed"&gt;&lt;/param&gt;\n        public void ResetRandomGenerator(int? seed)\n        {\n            random = seed.HasValue ? new Random(seed.Value) : new Random();\n        }\n    }\n}\n</code></pre>\n\n<p>Gist: <a href="https://gist.github.com/MrBogomips/ae6f6c9af8032392e4b93aaa393df447" rel="nofollow">https://gist.github.com/MrBogomips/ae6f6c9af8032392e4b93aaa393df447</a></p>\n'}, {'answer_id': 55612460, 'author': 'user2796283', 'author_id': 2796283, 'author_profile': 'https://Stackoverflow.com/users/2796283', 'pm_score': 0, 'selected': False, 'text': '<p>The implementation in the original question seems a little odd to me;</p>\n\n<p>The total weight of the list is 60 so the random number is 0-59.\nIt always checks the random number against the weight and then decrements it.\nIt looks to me that it would favour things in the list based on their order.</p>\n\n<p>Here\'s a generic implementation I\'m using - the crux is in the Random property:</p>\n\n<pre><code>using System;\nusing System.Collections.Generic;\nusing System.Linq;\n\npublic class WeightedList&lt;T&gt;\n{\n    private readonly Dictionary&lt;T,int&gt; _items = new Dictionary&lt;T,int&gt;();\n\n    // Doesn\'t allow items with zero weight; to remove an item, set its weight to zero\n    public void SetWeight(T item, int weight)\n    {\n        if (_items.ContainsKey(item))\n        {\n            if (weight != _items[item])\n            {\n                if (weight &gt; 0)\n                {\n                    _items[item] = weight;\n                }\n                else\n                {\n                    _items.Remove(item);\n                }\n\n                _totalWeight = null; // Will recalculate the total weight later\n            }\n        }\n        else if (weight &gt; 0)\n        {\n            _items.Add(item, weight);\n\n            _totalWeight = null; // Will recalculate the total weight later\n        }\n    }\n\n    public int GetWeight(T item)\n    {\n        return _items.ContainsKey(item) ? _items[item] : 0;\n    }\n\n    private int? _totalWeight;\n    public int totalWeight\n    {\n        get\n        {\n            if (!_totalWeight.HasValue) _totalWeight = _items.Sum(x =&gt; x.Value);\n\n            return _totalWeight.Value;\n        }\n    }\n\n    public T Random\n    {\n        get\n        {\n            var temp = 0;\n            var random = new Random().Next(totalWeight);\n\n            foreach (var item in _items)\n            {\n                temp += item.Value;\n\n                if (random &lt; temp) return item.Key;\n            }\n\n            throw new Exception($"unable to determine random {typeof(T)} at {random} in {totalWeight}");\n        }\n    }\n}\n</code></pre>\n'}, {'answer_id': 60995361, 'author': 'zhe', 'author_id': 90180, 'author_profile': 'https://Stackoverflow.com/users/90180', 'pm_score': 2, 'selected': False, 'text': "<p>A little bit too late but here's C#7 example. It's pretty small and gives correct distribution.</p>\n\n<pre><code>public static class RandomTools\n{\n    public static T PickRandomItemWeighted&lt;T&gt;(IList&lt;(T Item, int Weight)&gt; items)\n    {\n        if ((items?.Count ?? 0) == 0)\n        {\n            return default;\n        }\n\n        int offset = 0;\n        (T Item, int RangeTo)[] rangedItems = items\n            .OrderBy(item =&gt; item.Weight)\n            .Select(entry =&gt; (entry.Item, RangeTo: offset += entry.Weight))\n            .ToArray();\n\n        int randomNumber = new Random().Next(items.Sum(item =&gt; item.Weight)) + 1;\n        return rangedItems.First(item =&gt; randomNumber &lt;= item.RangeTo).Item;\n    }\n}\n</code></pre>\n"}, {'answer_id': 71134909, 'author': 'RWolfe', 'author_id': 3915050, 'author_profile': 'https://Stackoverflow.com/users/3915050', 'pm_score': 0, 'selected': False, 'text': '<p>Another option is this</p>\n<pre><code>private static Random _Rng = new Random();\npublic static Broker GetBroker(List&lt;Broker&gt; brokers){\n    List&lt;Broker&gt; weightedBrokerList = new List&lt;Broker&gt;();\n    foreach(Broker broker in brokers) {\n        for(int i=0;i&lt;broker.Weight;i++) {\n            weightedBrokerList.Add(broker);\n        }\n    }\n    return weightedBrokerList[_Rng.Next(weightedBrokerList.Count)];\n}\n</code></pre>\n'}, {'answer_id': 72568836, 'author': 'Chris', 'author_id': 8291038, 'author_profile': 'https://Stackoverflow.com/users/8291038', 'pm_score': 2, 'selected': False, 'text': '<p>June 2022: One more implementation (in c#) for the pile:</p>\n<p><a href="https://github.com/cdanek/KaimiraWeightedList" rel="nofollow noreferrer">https://github.com/cdanek/KaimiraWeightedList</a></p>\n<p><code>O(1)</code> gets (!), <code>O(n)</code> memory, <code>O(n)</code> add/removes/edits, robust (nearly all <code>IList</code> methods are implemented) and extremely easy to use (one C# file, one line of code to construct, one line of code to add items, one line of code to get an item):</p>\n<pre class="lang-cs prettyprint-override"><code>WeightedList&lt;string&gt; myList = new();\nmyList.Add(&quot;Hello&quot;, 1);\nmyList.Add(&quot;World&quot;, 2);\nConsole.WriteLine(myList.Next()); // Hello 33%, World 66%\n</code></pre>\n<p>Uses walker-vose alias method.</p>\n'}]
['https://Stackoverflow.com/questions/56692', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/2868/']