Tech Qu: Weighted picks from a list.

Write a function that given a list of items and weights return a random item in the list taking the weights into account.

The solution really depends if this is a one shot or a repeated call implementation.

Code Snippet

1. static Random rnd = new Random();
2.     public static int WeightedPick(int[] data)
3.     {
4.       var total = 0;
5.       foreach (var datum in data)
6.       {
7.         total += datum;
8.       }
9.       var pick = rnd.Next(total);
10.       var accu = 0;
11.       for (var i = 0; i < data.Length; i++)
12.       {
13.         accu += data[i];
14.         if (accu >= pick)
15.         {
16.         //DEBUG: Console.WriteLine(string.Format("rnd:{0}  item:{1}",pick,i));
17.           return i;
18.         }
19.       }
20.       return data.Length;
21.     }

 

The code actually had a bug on the first cut. If the rnd is in the function, values will repeat because multiple calls may happen in the same RANDOM interval for the seed. The solution was to use an external Random so each .Next would work onwards from the original seed.

 

Testing code is simple:

We repeat the procedure with a given distribution and see what the results are. We would expect 9000, 900 and 100.

Code Snippet

1. int[] testcase1 = {900, 90, 10};
2. var zCount=0;
3. var oCount=0;
4. var tCount = 0;
5. for(int i=0; i < 10000;i++)
6. {
7.   switch(Questions.WeightedPick(testcase1))
8.   {
9.     case 0:
10.       zCount++;
11.       break;
12.       case 1:
13.       oCount++;
14.       break;
15.       case 2:
16.       tCount++;
17.       break;
18.       default:
19.       throw new DataException("Out of bounds");
20.   }
21. }
22. Console.WriteLine(string.Format("0:{0} 1:{1} 2:{2}",zCount,oCount,tCount));

The results (from one run) was:

It works!