Calculating which item is next in a percentage distribution

I'm working on a project that involves diverting phone calls to a number of destinations.

For example, I want:

• 10% of calls to go to destination A
• 20% of calls to go to destination B
• 30% of calls to go to destination C
• 40% of calls to go to destination D

The number of destinations and their percentages must be configurable.

I've been thinking about how to do this, playing around with spreadsheets and some code, and I came up with this:

For each destination, take a random number, multiply it by the percentage, and select the destination with the highest number. Like this:

Item: RANDOM * PERCENTAGE = RESULT
   A:   48   *     10     =   480
   B:   33   *     20     =   660
   C:   81   *     30     =  2430  <--- Highest number, select C
   D:    5   *     40     =   200

I thought I'd worked it out as D would clearly be selected the most, followed by C, then B, and least of all A.

But it doesn't work. If I do this 5000 times, and calculate the actual percentage of times each destination was selected, I get this:

• 1% of calls to go to destination A
• 12% of calls to go to destination B
• 31% of calls to go to destination C
• 56% of calls to go to destination D

Here is the code I used to test this:

// Initialise item weighting percentages
Dictionary<string, int> weighting = new Dictionary<string, int>();
weighting["A"] = 10; //10%
weighting["B"] = 20; //20%
weighting["C"] = 30; //30%
weighting["D"] = 40; //40% (total = 100%)

// Initialise data set used for each iteration
Dictionary<string, int> data = new Dictionary<string, int>();

// Initialise counts of the selected items
Dictionary<string, int> count = new Dictionary<string, int>();
count["A"] = 0;
count["B"] = 0;
count["C"] = 0;
count["D"] = 0;

Random rand = new Random();

// Loop 5000 times
for (int i = 0; i < 5000; i++) {

    // For each item, get a random number between 0 and 99
    // and multiply it by the percentage to get a
    // weighted random number.
    data["A"] = rand.Next(100) * weighting["A"];
    data["B"] = rand.Next(100) * weighting["B"];
    data["C"] = rand.Next(100) * weighting["C"];
    data["D"] = rand.Next(100) * weighting["D"];

    // Find which item came out on top and increment the count
    string sel = data.First(x => x.Value == data.Max(y => y.Value)).Key;
    count[sel]++;

    // Log, so you can see whats going on...
    if (i < 15)
        Console.WriteLine("A:{0:00000}  B:{1:00000}  C:{2:00000}  D:{3:00000}  SELECTED:{4}",
            data["A"], data["B"], data["C"], data["D"], sel);
    else if (i == 15) Console.WriteLine("...");

}

// Output the results, showing the percentage of the number
// occurrances of each item.
Console.WriteLine();
Console.WriteLine("Results: ");
Console.WriteLine("    A = {0}%", 100 * ((double)count["A"] / (double)count.Sum(z => z.Value)));
Console.WriteLine("    B = {0}%", 100 * ((double)count["B"] / (double)count.Sum(z => z.Value)));
Console.WriteLine("    C = {0}%", 100 * ((double)count["C"] / (double)count.Sum(z => z.Value)));
Console.WriteLine("    D = {0}%", 100 * ((double)count["D"] / (double)count.Sum(z => z.Value)));

The results are:

A:00780  B:00300  C:01740  D:0开发者_JAVA技巧3680  SELECTED:D
A:00600  B:00660  C:00060  D:03400  SELECTED:D
A:00900  B:01880  C:00510  D:00720  SELECTED:B
A:00260  B:01380  C:00540  D:01520  SELECTED:D
A:00220  B:01960  C:00210  D:02080  SELECTED:D
A:00020  B:01400  C:01530  D:00120  SELECTED:C
A:00980  B:00400  C:01560  D:03280  SELECTED:D
A:00330  B:00300  C:01500  D:03680  SELECTED:D
A:00590  B:00460  C:02730  D:02400  SELECTED:C
A:00580  B:01900  C:02040  D:01320  SELECTED:C
A:00620  B:01320  C:00750  D:01760  SELECTED:D
A:00320  B:01040  C:01350  D:03640  SELECTED:D
A:00340  B:01520  C:02010  D:03880  SELECTED:D
A:00850  B:01420  C:00480  D:03400  SELECTED:D
A:00560  B:00680  C:00030  D:00000  SELECTED:B
...

Results: 
    A = 1.44%
    B = 11.54%
    C = 30.6%
    D = 56.42%

Can anyone suggest a way to fix this so that the real percentages come out as configured?

And for bonus points, can anyone suggest a way to do something similar but not using random numbers, so that the sequence of selected destinations is clearly defined. Using the example above would output this sequence every time:

ABCDBCDCDD ABCDBCDCDD ABCDBCDCDD ABCDBCDCDD ...

(note that the sequence is evenly distributed)

Thanks. Ben

Ok, I have done this numerous times before in simulations so here is the basic method I use (without proper error checking):

You need to imagine a line draw across the page going from 0 to 100. Now what we're doing is dividing this line up proportionally amongst your destinations. We then use random numbers to choose a point on this line. The destination which has that area of the line is the one selected.

EDIT: Attempt at line diagram

|-----------------------------------------------------|   Line 1 to 100
|-----|----------|---------------|--------------------|   Line split proportionally
0  A  10    B    30     C        60      D           100

We can do this as follows.

Assume your destination percentages are in an array, instead of in separate variables.

int totalPercentages = 0; 
int destinationsIndex = -1;
int randomNumberBetween0and100 = GetRandomNumber();
for(int i = 0; i < destinationPercentageArrays.Length; i++)
{
    totalPercentages += destinationPercentageArrays[i];
    if (totalPercentages > randomNumberBetween0and100)
    {
        destinationIndex = i;
        break;
    }
}

if (destinationIndex == -1)
{
   throw new Exception("Something went badly wrong.");
}

Now the variable destinationIndex points to the selected destination.

For a distribution by the percentages you gave do this:

Create a random number between 1 and 100 (inclusive)

If < 10 A
If > 10 < 30 B
If > 30 < 60 C
If > 60 D

As for the question of how to have a defined list, just put the destinations in order into an array and enumerate through them one at a time. When you run out, start again at the beginning.

string[] destinations = new string[] { "A", "B", "C", "D", ... }

int counter = 0;

//when need routing
RouteTo(destinations[counter]);
counter++;
if (counter == destinations.Length)
{
     counter = 0;
}

Another possibility is to fill a list, with size 100, using a for-loop and inserting each value times its weight. Then randomly select a list-item.

Example, short list (10 items)

• 5x A
• 4x B
• 1x C

List = {A,A,A,A,A,B,B,B,B,C}

Random between 0 and 9.

This will create a random list 100 characters long, ie ABCDBCDCDD...

    static void Main()
    {
        var weighting = new Dictionary<char, int>();
        weighting['A'] = 10; //10%
        weighting['B'] = 20; //20%
        weighting['C'] = 30; //30%
        weighting['D'] = 40; //40% (total = 100%)

        var test = CreateOrder(weighting);
    }

    static IEnumerable<char> CreateOrder(Dictionary<char, int> weighting)
    {
        var list = new List<KeyValuePair<int, char>>();
        var random = new Random();
        foreach (var i in weighting)
        {
            for (int j = 0; j < i.Value; j++)
            {
                list.Add(new KeyValuePair<int, char>(random.Next(), i.Key));
            }
        }
        return list.OrderBy(u=>u.Key).Select(u => u.Value);
    }