C# has several built-in methods for working with arrays and lists, but what if you need to randomize a list of items? In this article, we’ll look at some techniques we can use to randomize lists in C#. We’ll also discuss some of the pros and cons of each technique and assess how they perform.
Without further ado, let’s start!
Prerequisites
First, let’s define a function to generate a list of integers. We’ll use this when testing the different ways to randomize lists. The method accepts the list’s length as a parameter and returns a List<int> object:
public List<int> OrderedInts(int size)
{
var numbers = new List<int>();
for (int i = 0; i < size; i++)
{
numbers.Add(i);
}
return numbers;
}
Next, we are going to initialize a List<int> object containing 1,000,000 numbers in our test class, which we intend to shuffle using the strategies we discuss:
private readonly RandomizeGenericListsMethods _randomizeListObj;
private readonly List<int> _orderedList;
public RandomizeGenericListsUnitTests()
{
_randomizeListObj = new RandomizeGenericListsMethods();
_orderedList = _randomizeListObj.OrderedInts(1000000);
}
Let’s dive into some of the techniques we can use to shuffle List<T> objects in C#.
Fisher-Yates Shuffle Algorithm
This algorithm has both original and modern implementations. It’s worth familiarizing yourself with the Fisher-Yates Shuffle.
We are going to implement the modern implementation of the Fisher-Yates Shuffle algorithm:
Assuming we have an array num of n elements:
for i from n−1 iterating down to 1 do
k ← random integer that is 0 ≤ j ≤ i
swap num[k] with num[i]
When implementing this algorithm, we are going to start from the last element and swap it with a random element that we pick from the entire list. Then we proceed to reduce the size of the list by one and repeat the same process until we get to the first element.
First, let’s define and initialize an instance of the Random class for use in our examples:
private readonly Random _rand;
public RandomizeGenericListsMethods()
{
_rand = new Random();
}
Next, let’s proceed to implement our algorithm:
public List<int> GenerateRandomLoop(List<int> listToShuffle)
{
for (int i = listToShuffle.Count - 1; i > 0; i--)
{
var k = _rand.Next(i + 1);
var value = listToShuffle[k];
listToShuffle[k] = listToShuffle[i];
listToShuffle[i] = value;
}
return listToShuffle;
}
The algorithm has an O(N) time complexity as its runtime depends on the size of the list. We also assume that the Random class takes O(1) time to generate a number.
Finally, we can verify that we can successfully shuffle our List<int> object using the Fisher-Yates algorithm:
var shuffledList = _randomizeListObj.GenerateRandomLoop(_orderedList); var firstVal = shuffledList.First(); var lastVal = shuffledList.Last(); Assert.AreNotEqual(firstVal, 0); Assert.AreNotEqual(lastVal, 999999);
Alternatively, we can leverage existing libraries such as MoreLINQ to randomize our lists. The library has a Shuffle() method, which implements the Fisher-Yates algorithm to help us shuffle our lists.
Randomize a List using OrderBy Random Numbers
We can use the inbuilt random class in C# to shuffle a List<T> object in C# by invoking it with the OrderBy() method in a lambda expression.
To make our example simple, let’s define a method that accepts and randomizes a List<int> object:
public List<int> GenerateRandomOrderBy(List<int> listToShuffle)
{
var shuffledList = listToShuffle.OrderBy(_ => _rand.Next()).ToList();
return shuffledList;
}
The method invokes the OrderBy() and rand.Next() functions to shuffle the listToShuffle object by ordering it by random numbers.
Next, we can verify that our method successfully shuffles a list:
var shuffledList = _randomizeListObj.GenerateRandomOrderBy(_orderedList); var firstVal = shuffledList.First(); var lastVal = shuffledList.Last(); Assert.AreNotEqual(firstVal, 0); Assert.AreNotEqual(lastVal, 999999);
Shuffle a List using OrderBy by Guid Values
We use a similar strategy as the previous example, except that we substitute the Random class with the Guid.NewGuid() method in our OrderBy() clause:
public List<int> GenerateRandomOrderByGuid(List<int> listToShuffle)
{
var shuffledList = listToShuffle.OrderBy(_ => Guid.NewGuid()).ToList();
return shuffledList;
}
Let’s verify that we can shuffle our List<int> object with this strategy:
var shuffledList = _randomizeListObj.GenerateRandomOrderByGuid(_orderedList); var firstVal = shuffledList.First(); var lastVal = shuffledList.Last(); Assert.AreNotEqual(firstVal, 0); Assert.AreNotEqual(lastVal, 999999);
Performance Benchmarks
First, we are going to create a new object that generates a List<int> object to shuffle when performing these benchmarks:
public IEnumerable<List<int>> SampleList()
{
yield return OrderedInts(1000000);
}
We use the yield operator in our example to create the list on demand, which has some performance benefits.
Next, let’s analyze our benchmark results:
| Method | Mean | Error | StdDev | Rank | Allocated | |-------------------------- |----------:|----------:|----------:|-----:|-----------:| | GenerateRandomLoop | 24.92 ms | 1.645 ms | 4.798 ms | 1 | 24 B | | GenerateRandomOrderBy | 428.39 ms | 21.995 ms | 64.506 ms | 2 | 16000752 B | | GenerateRandomOrderByGuid | 699.60 ms | 28.362 ms | 79.994 ms | 3 | 28000688 B |
We can see that the Fisher-Yates algorithm is almost twenty times faster than the other Linq-based functions. The OrderBy() method implements the quicksort algorithm, which has a worst-case complexity of O(N2) while our Fisher-Yates algorithm implementation takes O(N).
Our Guid solution seems to be almost one and a half times slower than our Random solution because Guid values consume more memory, which affects how the algorithm performs.
What Are Some Benefits of Randomizing Lists?
First, creating random lists in C# helps us to easily create dynamic and flexible content for our applications.
Additionally, randomizing lists allows us to create more engaging user experiences by keeping things interesting and unpredictable.
Furthermore, this approach offers a number of performance benefits, since it doesn’t require us to store and manipulate large amounts of data.
Drawbacks of Creating Random Lists
One of the drawbacks of randomly generating lists is that there’s a tendency for the same elements to be repeated more often than would be ideal. This could potentially lead to suboptimal results when using these lists in applications, as certain elements will appear more frequently than others.
Conclusion
In this article, we learn how to randomize a list in C#. We can see that there are a few different ways to do this, and each has its benefits and drawbacks. We are looking forward to getting your feedback and learning together!