Evenly selecting items from a list in a pseudo random manner

• Download RandomSelection.zip - 14.3 KB

Introduction

Recently, I had a need to write code to randomly select items from a small list.

Given a list of items, ["R", "G", "B"], pick an item, "R", "G" or "B".

On the average, the pick needed to be made about 99 times for a given session. At the end of the session, I was hoping to pick R, G, and B approximately 33 times each (33 + 33 + 33 = 99).

.NET provides a System.Random class to randomly pick a number in a given range of values. The range of values I used was 0, 1, 2 corresponding to R, G, B. Unfortunately, using System.Random by itself did not yield an even distribution of picked values.

1. Some values were picked more often than others.
2. Sometimes, the same value was picked in consecutive picks. 

Therefore, I embarked on an effort to write a random selection algorithm that would address the above two shortcomings.  

Background

The following was my first attempt to write a class that randomly picks items from a list. 

public class RandomPickerSimple<T>
{
    private List<T> m_Items;
    private Random m_Random;

    public RandomPickerSimple(List<T> items)
    {
        this.m_Items = items;
        m_Random = new Random();
    }

    public T PickItem()
    {
        int pickedIndex = m_Random.Next(0, m_Items.Count);
        return m_Items[pickedIndex];
    }
}

Given a list, ["R", "G", "B"], I used the RandomPickerSimple class to make 99 picks. The following are the results of 3 runs.

 B R R B R G B R R G G B B B B R G R G G B G G G R B R G G B G R R B B R 
     B G G G G R G R B R R G G G B R G B B G B G B R G G G G R G B B R 
     G R R G B R G B R B R B G B R B G G G B R G R B R R B G B R
 "B":31 "G":37 "R":31

  G G G B G R G B G G B B G G R B B R R B R B G G R B B B B R G B R R G G 
    G R B G R G B G R B R R R G B G R B B G B R B G R G B G R B B G B G G B 
    G B B G R R R G G G B G G R B G G R G G R R G G B R G
 "B":31 "G":41 "R":27
 
  G R G R G B G R B G B B R G R G G R R R B R B G B B R B B R G G G R B R 
    R G R G R G G R B R R G G B B B R R B R R R G G G B G B B G R R G B G B R 
    B B G B B G G B B R R R B G G R G R R R G B R R G R
 "B":29 "G":33 "R":37 

As evident from the above results: 

• Items are not evenly picked. For example, in the last run "B" is picked 29 times whereas "R" is picked 37 times. 
• Same item is selected in consecutive picks. Note the consecutive picked values of "R R R", "G G G", and "B B B" in the last run.

A more sophisticated RandomPicker  

To pick items more evenly, I made the following adjustments.

public class RandomPicker<T>
{
    private Dictionary<T, int> m_Items;
    private Random m_Random;
    private T m_LastPick;

    public RandomPicker(List<T> items)
    {
        if (items.Count < 2)
            throw new ArgumentOutOfRangeException("The list must contain at least two items.");
        this.m_Items = new Dictionary<T, int>();
        items.ForEach(x => this.m_Items.Add(x, 0));
        m_Random = new Random();
    }

    private List<T> GetCandidateList()
    {
        int minOccur = m_Items.Values.Min();
        var list = m_Items.Keys.Where(x => m_Items[x] == minOccur).ToList();
        list.Remove(this.m_LastPick);
        if (list.Count < 1)
        {
            list = m_Items.Keys.ToList();
            list.Remove(this.m_LastPick);
        }
        return list;
    }

    public T PickItem()
    {
        var candidateList = GetCandidateList();
        int pickedIndex = m_Random.Next(0, candidateList.Count);
        m_Items[candidateList[pickedIndex]]++;
        m_LastPick = candidateList[pickedIndex];
        return candidateList[pickedIndex];
    }
}

The key improvements are as follows.

1. The class keeps track of how many times an item has been picked (in m_Items dictionary). 
2. The class builds a candidate list of items based on how many times an item has been selected in previous picks (see GetCandidateList() method).  
3. The class remembers the last pick so as not to pick the same item in the consecutive picks (see m_LastPick variable).  

Given a list, ["R", "G", "B"], I used the RandomPicker class to make 99 picks. The following are the results of three runs: 

 B R G B G R G R B G B R B G R G R B R G B R B G R 
  B G R B G R B G R G B G B R B G R G B R G B R B G R B G R 
  B G R G B R G B R B G R B G R B G R G R B G B R G R B G B R G R B G R B R G B G B R B G R
 "B":33 "G":33 "R":33

  G B R G B R G B R G B R G R B G B R G R B R G B R B G B G R B G R 
   G R B R B G B G R B R G R B G B G R G B R G R B R B G R B G R B G B G R B R G 
   B G R G B R B R G B R G R G B R G B G R B G B R G B R
 "B":33 "G":33 "R":33

  R B G B R G R G B G R B G B R B R G B G R B R G B R G B R G R B G B G R B 
   R G B G R G B R G R B G B R G R B R B G R B G R B G R B G R B G B R 
   G B G R B R G B R G B G R B R G R B G B R G R B G R G B
 "B":33 "G":33 "R":33 

As evident from the above results:   

• Items are picked more evenly. In all three runs, "R", "G", and "B" each are picked 33 times. 
• Same items are not picked in consecutive picks.

To further validate the results, I ran the random selection test against a list of integers, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]. The result of the run is as follows (99 picks).

 10 3 12 1 11 2 5 8 7 9 4 6 12 2 3 4 11 6 5 8 10 7 9 1 12 10 11 4 
      5 7 1 9 2 3 8 6 12 4 10 1 6 3 2 11 9 8 7 5 7 9 8 6 5 12 1 4 10 11 2 3 2 10 4 12 11 
      5 1 9 3 7 6 8 6 1 2 11 4 12 5 3 7 8 10 9 1 7 5 4 2 9 6 3 8 12 11 10 12 2 11
 "1":8 "2":9 "3":8 "4":8 "5":8 "6":8 "7":8 "8":8 "9":8 "10":8 "11":9 "12":9 

The results show integers from the list are picked evenly, without repetition of the same integer in consecutive picks.   

Points of Interest  

Over a large number of attempts (say, 100,000+), the RandomPickerSimple produces a fairly even distribution of picks. However, for smaller number of picks, the results can be quite uneven. RandomPicker attempts to produce an even distribution of item selection over a smaller number of picks.  

[Update Dec 3, 2013]  

As many commentators noted (thanks for your comments!), this algorithm is not a purely random algorithm in the mathematical sense. Just the fact that the last item selected has no chance of being selected in the next pick violates the definition of randomness. There were three primary goals for this algorithm.

1. Add a degree of randomness when picking items from the list 
2. Do not select the same item in consecutive picks  
3. After a number of picks, all items in the list should have been picked evenly 

The Visual Studio solution containing the classes and tests is attached to this article.  

History  

• First revision.
• Changed title to more clearly reflect the purpose of the code. Added clarification to Points of Interest.