Monday, November 17, 2008

Shuffling arrays in C#

Have you ever had a need to output some array of objects in a random order? Say a array of strings ... with 52 elements that each represent a playing card?

Well, if you have ever had a need to shuffle the elements in an array, you have probably found that there are only a few different algorithms: Either card swapping or assigning a random Key to each element and then sorting by the key.

Unfortunately there are quite a few issues involved with the swap shuffle so I wanted a to use the sort version. Well, what has tuples? Hashtables? Hashtables! So, how do you sort a Hashtable? Hmmmm, maybe I need to think harder about this.

Hey, did everyone realize their is a sorted version called a SortedList?

OK, So we will use the SortedList. Now I want this function to use Generics so that it will take an array of any type. So lets try!

(Mind you that this is not nearly as small as the implementation here but I am not posting here to show how to shuffle in the least number of lines or use the latest technology, but with an eye towards the most understandable source.)

private static T[] Shuffle <T> (T[] OriginalArray)
{
var matrix = new SortedList();
var r = new Random();

for (var x = 0; x <= OriginalArray.GetUpperBound(0); x++)
{
var i = r.Next();

while (matrix.ContainsKey(i)) { i = r.Next(); }

matrix.Add(i, OriginalArray[x]);
}

var OutputArray = new T[OriginalArray.Length];

matrix.Values.CopyTo(OutputArray, 0);

return OutputArray;
}

2 comments:

Unknown said...

There's a bug in your code. I'm working on it. One of the items in the shuffled array ends up null.

Unknown said...

sorry.. no bug in your code. a bug in my code :)