All my work for school is handed in, now I just have to make a few requisite appearances for a reading or two and a screening. Ooh yeah!

The Holiday Season! Christmas time is surely the best time of the year to sit at home and program! Wait… why is there a glowing tree in my– Why am I wearing a sweat– Who put eggnog in– AAAAAAAAAAAAHHHHHHHHHHHHHHHHHHHHHHH!

Long story short, mid-way through setting up Visual C# Express(Pro around here somewhere…) for use with XNA I decided to make a simple WindowForms App(ooh, shiny!). I’ve used Netbeans before, so I stumbled through it with grace and had a few little duh-moments with Visual Studio adding the code (machines… programming machines… scary shit man.) for me and all that Let’s-Help-Christian do it our way.

A simple enough program; get some text from the top, the users clicks a button and gets it all garbled up below. Then it sort of occurred to me: “Hey! I’ve never written my own shuffle algorithm, what’s the best way to do this?” …and they all went skipping down the yellow brick road to Google.

So after looking at a few threads here and there about shuffling I came to this blog post about naive shuffling algorithms. (It’s pretty good, read it.)

Jeff Atwood goes on to explain how a simple shuffling algorithm, which was strikingly similar to what I was thinking of using, becomes extremely biased when taken to the extreme. This isn’t just because random numbers aren’t random, it’s because simply iterating through an array and swapping it with another random index, for each item in the array creates more random possibilities than naturally exist.

Jeff uses an example of 3 playing cards. 3 playing cards have

3 + 2 + 1 = 6

possibilities. However swapping each position with potentially every other position creates

3 + 3 + 3 = 9

possibilities. 6 does not divide into 9 evenly, so there will always be a few possibilities that weigh higher than the others.

For the solution he points us to the Knuth Shuffle (which brought back a long forgotten memory of this being brought up in a class at some point as the Fisher-Yates algorithm) which states(borrowed(I’ll give it back(maybe)) from the Wikipedia page):

To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

Jeff provides an example on his page which I’ve adapted for my strings:

public static void Shuffle(ref char[] letters)
{
   //Get a random number from the future!
   Random rand = new Random(System.DateTime.Now.Millisecond + 3);
   for (int i = letters.Length - 1; i > 0; --i)
   {
      //Get a random number that can include i
      int n = rand.Next(i + 1);
      //Trading places
      char swap = letters[i];
      letters[i] = letters[n];
      letters[n] = swap;
   }
}

Check it out! ShuffleText(exe, needs .NET4)

This weekend, I’m going to try to get a simple game going in XNA. If I can find it I might remake my Shwack-A-Mole game.