June 7, 2010

Two Ways to Randomize IList Objects

I recently developed a self-sorted IList implementation for a project and I needed some automated way to unit test it - so naturally, the best way to automatically test a sorting function is to force it to sort the results of an unsorting function ;). Just for reference, IList is the interface implemented by every sort of List<T> variant in the .NET Collections library, with the notable exception of SortedList which is really a misnomer given that it actually implements IDictionary instead of IList.

I was excited at the prospect of developing my own unsorting method, but sadly a quick Bing query revealed a couple of solutions developed by programmers far more diligent than I, and I decided to roll both of their solutions into a pair of generic extension methods which I have tested and built into my solution. Let's take a look at them:

Solution 1 - Randomizing an IList<T> Object Using LINQ Projection

By far the most simple, yet elegant method for randomizing the contents of an IList object I found was this one developed by Sven Groot, which uses LINQ's OrderBy method to randomize the contents of an IEnumerable object:

public static IEnumerable<T> Randomize<T>(this IEnumerable<T> source)
{
    Random rnd = new Random();
    return source.OrderBy<T, int>((item) => rnd.Next());
}

In terms of brevity, it doesn't get much better than this. Also, given that I need to ultimately create an IList<T> object out of this randomized collection remember that List<T> has a constructor which accepts an IEnumerable<T> collection as an argument.

Solution 2 - Randomizing an IList<T> Object Using an Index Swap Routine

The more traditional, pre-LINQ solution would be to randomize the contents of an IList<T> object using a swap routine given that all IList objects have indexers, which is exactly what Jon Skeet did using this solution:

Random rng = new Random();
for (int i = list.Count - 1; i > 0; i--)
{
    int swapIndex = rng.Next(i + 1);
    if (swapIndex != i)
    {
        //Changed this from "object" to "T" in order to support generics.
        object tmp = list[swapIndex];
        list[swapIndex] = list[i];
        list[i] = tmp;
    }
}

If you have time, make sure you read Jon's explanation of how the algorithm works (it's pretty cool imho.) I went ahead and wrapped this code into an extension method just like Sven's LINQ solution, and here's what that looks like:

public static IEnumerable<T> RandomizeWithSwaps<T>(this IList<T> list)
{
    Random rng = new Random();
    for (int i = list.Count - 1; i > 0; i--)
    {
        int swapIndex = rng.Next(i + 1);
        if (swapIndex != i)
        {
            //Changed this from "object" to "T" in order to support generics.
            T tmp = list[swapIndex];
            list[swapIndex] = list[i];
            list[i] = tmp;
        }
    }

    return list;
}

One thing worth noting is that this extension method will only work with IList types - IEnumerable doesn't have any support for indexers, thus this extension method is somewhat wonky. Given that, I went with using the LINQ solution in my unit testing code.

Discussion, links, and tweets

I'm the CTO and founder of Petabridge, where I'm making distributed programming for .NET developers easy by working on Akka.NET, Phobos, and more..