LINQ Exchange

There are many times when we need to randomly sort a list or array. An example might be if you had a list of advertisements to display on your website, and need to randomly sort the list so the ads appear in random order. Another example might be if you have a card game, you need to randomly shuffle the cards between sets.

The first idea most people have for randomly sorting lists and arrays is to use Random.Next().  The main problem with using Random.Next() is that it is not really random. First, if you continue to use the same seed (the optional parameter when creating the Random object), you will always have the same series of results from Next(). Also, within a given seed, the result series isn't really random, it only appears random. There are many tools available for predicting the next number in a Random.Next() sequence.

Given all this, it is especially important to use a true random sort for arrays if you are doing important or security related work (such as shuffling the deck or cards, or generating random passwords).

There are number of different methods for sorting the array.  If you are populating your array from SQL Server 2005, you can add a order by clause on NewID

ORDER BY NEWID()

This will randomly sort the return results before the results leave the SQL Server engine.

We don't always get our list from SQL Server 2005, so I propose the following method to randomly sort an array using LINQ.

Randomly Sort a List Array With LINQ OrderBy

// create and populate the original list with 1000 elements
List<int> MyList = new List<int>(1000);
for (int i = 0; i < 1000; i++)
    MyList.Add(i);

// use System.GUID to generate a new GUID for each item in the list
List<int> RandomList = MyList.OrderBy(x => System.Guid.NewGuid()).ToList();

The important part to notice here is the use the System.Guid.NewGuid() function call. This returns a new GUID for each item in the array. Since GUID's are unique and non-repeating, this guarantees each item has a unique id. LINQ OrderBy will then sort the array by the list of GUID's returned.

Using the NewGUID() approach yields the same distribution spread as the Fisher-Yates Shuffle Algorithm. The distribution spread is the ratio of the possible outcomes to the actual permutations (how many possible combinations exists versus how many the random sort can make). Using Random.Next() does not return the possible outcomes. Random.Next has a naive distribution spread.

No related posts.

Related posts brought to you by Yet Another Related Posts Plugin.