Fisher-Yates shuffle as a generic list extension in C#

The Fisher-Yates shuffle is just a simple way of randomising the order of the contents of a list. For one of my last projects I had need to do this in C#, on lists of various types, so I decided to do it as an extension to a generic list, using templates. Now I should say from right off that Microsoft do not generally recommend that you extend existing .Net types, just in case they change them in the future which may break your code. However that wasn’t a worry for me in this project, and judging by the amount of people on the web giving examples of extending basic types and classes it isn’t a worry for them either. It looks cool anyway. πŸ™‚

Here is the code for the extension:

 public static class ListExtensions
    {
        /// <summary>
        /// Shuffle this list
        /// </summary>
        public static void Shuffle<T>(this List<T> thisList, Random RandomNumberGenerator)
        {
            for (int i = thisList.Count - 1; i >= 0; i--)
            {
                int j = RandomNumberGenerator.Next(0, i);
                T tmp = thisList[i];
                thisList[i] = thisList[j];
                thisList[j] = tmp;
            }
        }

        /// <summary>
        /// Return a shuffled copy of this list (leaves this list as it was)
        /// </summary>
        public static List<T> ShuffleAndCopy<T>(this List<T> thisList, Random RandomNumberGenerator)
        {
            T[] shuffled = new T[thisList.Count];
            thisList.CopyTo(shuffled);
            for (int i = shuffled.Count() - 1; i >= 0; i--)
            {
                int j = RandomNumberGenerator.Next(0, i);
                T tmp = shuffled[i];
                shuffled[i] = shuffled[j];
                shuffled[j] = tmp;
            }

            return shuffled.ToList();
        }

        /// <summary>
        /// Shuffle this list
        /// </summary>
        public static void Shuffle<T>(this List<T> thisList)
        {
            Random RandomNumberGenerator = new Random();

            for (int i = thisList.Count - 1; i >= 0; i--)
            {
                int j = RandomNumberGenerator.Next(0, i);
                T tmp = thisList[i];
                thisList[i] = thisList[j];
                thisList[j] = tmp;
            }

        }

        /// <summary>
        /// Return a shuffled copy of this list (leaves this list as it was)
        /// </summary>
        public static List<T> ShuffleAndCopy<T>(this List<T> thisList)
        {
            Random RandomNumberGenerator = new Random();

            T[] shuffled = new T[thisList.Count];
            thisList.CopyTo(shuffled);
            for (int i = shuffled.Count() - 1; i >= 0; i--)
            {
                int j = RandomNumberGenerator.Next(0, i);
                T tmp = shuffled[i];
                shuffled[i] = shuffled[j];
                shuffled[j] = tmp;
            }

            return shuffled.ToList();
        }

       
    }

There are two methods, Shuffle() which shuffles the current list and ShuffleAndCopy() which leaves the current list as it is and returns a shuffled copy. The reason I did two overrides for each are perhaps obvious if you know how the random number generator works, but I’ll tell you anyway. πŸ™‚ One of the methods declares a random number generator internally. This is OK provided that you are only likely to call it less than once a second. If you call it more frequently than that then the random number generator actually starts from the same number, so you find that the list are always shuffled in the same way. To get around that I created an override that allowed me to pass in a random number generator. In a Winforms app this could perhaps be declared within the main Program class, and in a web app perhaps within the Application state (I’ve only tried the former!).

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: