Random weighted choice

Question

Consider the class below that represents a Broker:

``````public class Broker
{
public string Name = string.Empty;
public int Weight = 0;

public Broker(string n, int w)
{
this.Name = n;
this.Weight = w;
}
}
``````

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

What do you think of the code below?

``````class Program
{
private static Random _rnd = new Random();

public static Broker GetBroker(List<Broker> 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 <= broker.Weight)
{
selectedBroker = broker;
break;
}

randomNumber = randomNumber - broker.Weight;
}

return selectedBroker;
}

static void Main(string[] args)
{
List<Broker> brokers = new List<Broker>();

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

while (true)
{
Dictionary<string, int> result = new Dictionary<string, int>();

Broker selectedBroker = null;

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

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();
}
}
}
``````

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

Is there a more accurate algorithm?

Thanks!

1
53
9/11/2008 2:34:11 PM

Your algorithm is nearly correct. However, the test should be `<` instead of `<=`:

``````if (randomNumber < broker.Weight)
``````

This is because 0 is inclusive in the random number while `totalWeight` is exclusive. In other words, a broker with weight 0 would still have a small chance of being selected – not at all what you want. This accounts for broker A having more hits than broker D.

Other than that, your algorithm is fine and in fact the canonical way of solving this problem.

34
9/11/2008 2:45:27 PM

How about something a little more generic, that can be used for any data type?

``````using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

public static class IEnumerableExtensions {

public static T RandomElementByWeight<T>(this IEnumerable<T> sequence, Func<T, float> weightSelector) {
float totalWeight = sequence.Sum(weightSelector);
// The weight we are after...
float itemWeightIndex =  new Random().NextDouble * totalWeight;
float currentWeightIndex = 0;

foreach(var item in from weightedItem in sequence select new { Value = weightedItem, Weight = weightSelector(weightedItem) }) {
currentWeightIndex += item.Weight;

// If we've hit or passed the weight we are after for this item then it's the one we want....
if(currentWeightIndex >= itemWeightIndex)
return item.Value;

}

return default(T);

}

}
``````

Simply call by

``````    Dictionary<string, float> foo = new Dictionary<string, float>();