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:
I’m not sure what Jeff’s definition of “naive” is, but it seems to be “missing a fundamental point of logic” aka “wrong”
The definition is specified in the first paragraph:
A naive 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. Nave algorithms usually consume larger amounts of resources (time, space, memory accesses, …), but are simple to devise and implement.
It shouldn’t be wrong, just inefficient.
In the naive algorithm an array element can change its value many times but in the KFY it can change it only once! Thats the difference. Thats why the naive algorithm leaks!
A red herring. This is true of the KFY algorithm as well; the “swap with yourself” step is valid in each iteration.
Funny, I usually don’t do well with complex math issues, but I understood this problem easily.
Thank you-- neither do I! Not all of us can be Wesner Moise, after all… 
In the naive algorithm an array element can change its value many times but in the KFY it can change it only once! Thats the difference. Thats why the naive algorithm leaks!
A red herring. This is true of the KFY algorithm as well; the “swap with yourself” step is valid in each iteration.
Surely the real moral of the story here is never use your own algorithm? We all know we should never write our own sort(), as the standard library will contain one that’s far more efficient and correct than anything we could think of. Surely that logic extends here? Is it not the case that when we need an algorithm to search, shuffle or sort, we should be copying them out of textbooks instead of navely assuming we can do just as well as theoretical computer scientists?
I’m not saying that we shouldn’t make an attempt to understand the algorithms we use; obviously not – you should never write code you don’t understand. But the academics covered this ground a long time ago; let’s not ignore their work.
Interesting post. As David House, I conclude it as “know thou libraries”.
std::random_shuffle for the win 
The proper algorithm must have been known since at least the sixties, so it would be strange if anything else was used in libraries.
Simple explanation through mathematical induction.
The singleton case with 1 card is perfectly shuffled (unbiased).
Assuming shuffling is unbiased with the n-1th case, let’s try shuffling n items.
Well we know that for the nth item, we want a 1/n probability of having any card be the nth card. So, we pick a random card from the n cards and let it be the nth card.
Then we attempt to shuffle the n-1 remaining cards, but we know by our inductive hypothesis, that shuffling n-1 cards via same method is also unbiased and this hypothesis is also true for the base case of 1 card. So, it’s true for all n = 1.
Nice one. I too found it slightly hard to grasp, but you do a good job of explaining the logic behind it!
Before everyone starts doing a maths demo, lets stick to the point.
The Danger of Navet
Is not so much that we all want to shuffle a pack of cards, but the story is educational. How many people would ever really test the shuffling of the pack prior to shipping product ? Of course if the project was open source eventualy the error would be corrected. If the project is closed source, the probablity is that the mistake would never ever be spotted.
Now since Open versus Closed is still debated . . . I have made the choice to focus on that singular aspect. To be fair, testing is not answered by either methodology.
Quick question… because I’m not a C# programmer.
In the example, you have “rand.Next(cards.Length)”… so how does that translate to “rand.Next(2)” in a 3 card deck?
Shouldn’t it be “rand.Next(3)”… which will give a random number of 0, 1 or 2?
Ref for rand.Next:
http://shepherdsbush.dcs.hull.ac.uk/wiki/index.php/Random_Numbers
I work in an industry where randomness is our bread and butter. Every application we create is rigorously tested, and then simulated with well over several billion iterations. Finally, if it doesn’t pass the chi-square test, we start all over again. A Chi-Squared test basically checks if we are too random, since thats not natural either
I think folks praising Python for not screwing this up have rather low expectations.
Great post. Simple and direct to the point of bad (or rather nave) programming. This is definitely the kind of geeky stuff that we “alpha” programmers truly love. Keep up the great work!
I have always done my array shuffle the later way you mentioned above only now after reading your post I realized that it has a name, Knuth-Fisher-Yates. I always think how to construct an algorithm using a model related to what we were taught in mathematics. In this case, combinatorial arrangement of numbers gives the best model. Just think as an event where one number will be chosen each at a time to fill in one position, and the rest is just how good you manipulate it to fit your programming language limitation and syntax.
I wonder what PHPs shuffle() might use.
While I recognize the truth in the article, like you I found it incredibly counter-intuitive. I thought for sure that only choosing values of n within the range “i” hasn’t been assigned to yet would yield some sort of bias- Being that some cards wouldn’t be moved as many times as others (since whatever got moved to cards[i] in each iteration would stay there), I thought for sure that there would be some way to predict, based on the order of the starting deck, at least the probability of each card being closer to the front or the back of the deck.
Thanks for the explanation! I like when being wrong is so fascinating.
Just wanted to pipe in that python’s random.shuffle() does use the Fisher-Yates algorithm.
Neat example, thanks! I found myself shaking my head the other day at some code that thought it could improve on Java’s random (not that somebody else couldn’t) but in fact generated alarmingly short repeating patterns in very short order. Now I find others shaking their heads at the shuffle algorithm I’ve used for years. My shop is extremely strong on business knowledge, but apparently weak at the CS and math skills needed to spot something like this!
Awesome post, been watching your blog for a few weeks now and it’s my first comment. Keep up this amazing work.
I’ve got the same question as Craig Francis, how does “rand.Next(cards.Length)” translate to “rand.Next(2)” in a 3 card deck?
Also, those graphics you made are very very good, which library or module did you use to output them?
This article assumes that rand has a perfectly random distribution. In a lot of environments, I rather doubt that it does. I have implemented the ‘naive’ version of this algorithm when I just needed something scrambled in a hurry and didn’t have time to research the proper algorithm. As a one-off, it is a perfectly serviceable solution and more than good enough given the vagaries of the various random number generators out there.
Not that I’m arguing against correctness. But there is also engineering practicality.