Naive Algorithms

Fascinating article about things that sound easy, but aren't. they are easy to implement wrong. Shuffling cards is one of those things. [Link]

In my previous post on shuffling, I glossed over something very important. The very first thing that came to mind for a shuffle algorithm is this:

for (int i = 0; i < cards.Length; i++)
{
   int n = rand.Next(cards.Length);
   Swap(ref cards[i], ref cards[n]);
}

It's a nice, simple solution to the shuffling problem:

1. Loop through each card in the deck.
2. Swap the current card with another randomly chosen card.

At first blush, this seems like a perfectly reasonable way to shuffle. It's simple, it's straightforward, and the output looks correct. It's the very definition of a naïve algorithm:

A naïve algorithm is a very simple solution to a problem. It is meant to describe a suboptimal algorithm compared to a "clever" (but less simple) algorithm. Naïve algorithms usually consume larger amounts of resources (time, space, memory accesses, ...), but are simple to devise and implement.

An example of a naïve algorithm is bubble sort, which is only a few lines long and easy to understand, but has a O(n²) time complexity. A more "clever" algorithm is quicksort, which, although being considerably more complicated than bubble sort, has a O(n log n) average complexity.

But there's a deep, dark problem with this naïve shuffling algorithm, a problem that most programmers won't see. Do you see it? Heck, I had the problem explained to me and I still didn't see it.

Testing it is the only way to see the problem.

This made me think of a program I wrote a few years ago, a dice roller for the RPG Godlike. The way dice were rolled was fairly unique, so I spent a few hours making a program that handled it. 10 sided dice were rolled, never more than 10 at a time, and matches were collected. Any 1s, 2s, 3s, etc. I made a die class that I could roll using the random function. I wanted to make sure the die was balanced, so I made 10 buckets and had the die rolled about 100,000 times, incrementing a bucket for each number. I could then see that the random number generator was balanced, so my dice were balanced.
I also displayed the likelihood of a roll being successful. This could be complicated as you could require 2, 3, 4 or more matches per success as well as ignoring matches of any value less than a specified number. I made a thread that continually rolled the dice with the options and calculated successes compared to the number of total rolls. That was a sub-optimal solution, I should have researched the math to calculate the success, but making the thread was easier, plus I wanted to practice multi threading a program.
All in all, it was a learning experience.