14,640,670 members
Articles » General Programming » Algorithms & Recipes » Algorithms
Article
Posted 2 Dec 2013

23.8K views
5 bookmarked

# Evenly selecting items from a list in a pseudo random manner

Rate this:
3 Dec 2013CPOL
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

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

## Share

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.

 First Prev Next
 My vote of 5 Dace29-Apr-15 2:15 Dace 29-Apr-15 2:15
 My vote of 2 Member 85404479-Dec-13 18:12 Member 8540447 9-Dec-13 18:12
 Ditto KP Lee9-Dec-13 15:48 KP Lee 9-Dec-13 15:48
 Permutations not random johannesnestler2-Dec-13 23:50 johannesnestler 2-Dec-13 23:50
 Is this really random? George Swan2-Dec-13 22:02 George Swan 2-Dec-13 22:02
 Not really random JV99992-Dec-13 21:30 JV9999 2-Dec-13 21:30
 Random bfrthekid992-Dec-13 21:04 bfrthekid99 2-Dec-13 21:04
 Last Visit: 26-Sep-20 14:32     Last Update: 26-Sep-20 14:32 Refresh 1