Click here to Skip to main content
Click here to Skip to main content

Evenly selecting items from a list in a pseudo random manner

, 3 Dec 2013 CPOL
Rate this:
Please Sign up or sign in to vote.
How to fairly pick items from a list

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. 

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Sal Razzaq
Technical Lead
United States United States
Sal Razzaq is a software engineer based in Carlsbad, California specializing in accounting and billing systems. Sal has a BS in Finance from Kansas State University, a Masters in Accounting Science from the University of Illinois at Urbana-Champaign and a Masters in Computer Science from the University of Illinois at Urbana-Champaign.

Comments and Discussions

 
GeneralMy vote of 2 PinmemberMember 85404479-Dec-13 18:12 
QuestionDitto PinmemberKP Lee9-Dec-13 15:48 
QuestionPermutations not random Pinmemberjohannesnestler2-Dec-13 23:50 
QuestionIs this really random? PinmemberGeorge Swan2-Dec-13 22:02 
QuestionNot really random PinmemberJV99992-Dec-13 21:30 
QuestionRandom Pinmemberbfrthekid992-Dec-13 21:04 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.141015.1 | Last Updated 3 Dec 2013
Article Copyright 2013 by Sal Razzaq
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid