Shuffling the Wrong Way

You may be wondering why we need a special algorithm for shuffling. What’s wrong with, say, the following alternative approach that I’ve invented off the top of my head? Here’s my proposed algorithm:

Similar to the Fisher-Yates Shuffle, let’s point to each of the array’s values and swap them with other values. However, we won’t constrain ourselves and only choose a value to the right of the pointer. Rather, we can swap each value with any other value—even those to the left of the pointer.

Here would be the code for this approach, which I’ll call “naïve shuffling”:

	import random


	def naive_shuffle(array):
	for i in range(0, len(array) - 1):
	j = random.randint(0, len(array) - 1)
	array[i], array[j] = array[j], array[i]

	array = [1, 2, 3, 4, 5, 6, 7, 8]
	naive_shuffle(array)
	print(array)

Indeed, when I run the code, I get an array that looks shuffled. So, what exactly is wrong with naïve shuffling?

In truth, the problem is so subtle that it’s terribly easy to overlook. But here’s the thing: if we want an algorithm to be truly random, we must ensure that every possible result of shuffling is equally likely to occur.

For example, imagine that we have a six-sided die. But instead of having sides marked from 1 to 6, we have five sides marked 1, 2, 3, 4, and 5, and the sixth side is an extra 5. While the result of the die roll will certainly be random, it won’t be perfectly random since the die is more likely to land on a 5 than any other number. This hurts the uniformity of the possible results, thereby hampering the die’s randomness.

We have to apply the same analysis to shuffling. If we’re shuffling the array [1, 2, 3], there are six possible permutations we can end up with:

	[1, 2, 3] [1, 3, 2]
	[2, 1, 3] [2, 3, 1]
	[3, 1, 2] [3, 2, 1]

Just like the die, we want to make sure that each of these six possibilities is equally likely to result from our shuffling algorithm. We don’t want a situation where one of these permutations is more likely to occur than the others.

With that in mind, let’s now analyze our proposed naïve shuffling algorithm using the same example array of [1, 2, 3].

With naïve shuffling, we point to each value in the array and “roll a die” by choosing a random index from anywhere in the array to swap it with. In our example, this is like rolling a three-sided die and getting the possible results of 0, 1, or 2. This will result in combinations such as 1, 2, 0 or 2, 2, 1 or 0, 0, 0. There are, in fact, 27 possible sets of random numbers that may be chosen. Here goes:

	0, 0, 0 --- 1, 1, 1 --- 2, 2, 2
	1, 0, 0 --- 0, 1, 0 --- 0, 0, 1
	2, 0, 0 --- 0, 2, 0 --- 0, 0, 2
	1, 1, 0 --- 1, 0, 1 --- 0, 1, 1
	1, 1, 2 --- 1, 2, 1 --- 2, 1, 1
	2, 2, 0 --- 2, 0, 2 --- 0, 2, 2
	2, 2, 1 --- 2, 1, 2 --- 1, 2, 2
	0, 1, 2 --- 0, 2, 1 --- 1, 0, 2
	1, 2, 0 --- 2, 1, 0 --- 2, 0, 1

To be clear, these aren’t the permutations of the results of the shuffle itself. These are the possible combinations of random indexes (die rolls) that we’ll generate throughout our shuffle.

Now, if we take each of these permutations and compute the result of the shuffle for each permutation, we get:

	[3, 1, 2] --- [2, 3, 1] --- [3, 1, 2]
	[3, 2, 1] --- [3, 2, 1] --- [2, 3, 1]
	[1, 3, 2] --- [2, 3, 1] --- [2, 1, 3]
	[3, 1, 2] --- [1, 3, 2] --- [1, 3, 2]
	[2, 1, 3] --- [2, 1, 3] --- [3, 1, 2]
	[2, 1, 3] --- [2, 3, 1] --- [1, 3, 2]
	[3, 2, 1] --- [3, 2, 1] --- [2, 3, 1]
	[1, 2, 3] --- [1, 2, 3] --- [1, 2, 3]
	[1, 3, 2] --- [1, 2, 3] --- [2, 1, 3]

If we take a tally of how many times each of the shuffling results occurs, we get:

	[1, 2, 3] -> 4 times
	[1, 3, 2] -> 5 times
	[2, 1, 3] -> 5 times
	[2, 3, 1] -> 5 times
	[3, 1, 2] -> 4 times
	[3, 2, 1] -> 4 times

Aha! It turns out that our naïve shuffling algorithm will produce three of the permutations more often than the other three permutations. This means that our algorithm doesn’t produce uniformly random results.

The Fisher-Yates Shuffle, on the other hand, does, and here’s why.

For an array of size 3, with Fisher-Yates, we only generate two random numbers. Again, this is because we don’t bother to generate a random number when we’re up to the final value in the array. As we tally all the possible permutations of random numbers, we should also keep in mind that the range of random numbers decreases as we progress through the array. For example, when we’re at the first value, we’ll generate a random number between 0 and 2. But when we’re pointing to the second value, the algorithm will only generate a number between 1 and 2.

Based on this, here are all the permutations of die rolls we might get in our example of shuffling an array of size 3:

	0, 1
	0, 2
	1, 1
	1, 2
	2, 1
	2, 2

We have only six permutations. When we compute the results of shuffling based on the die rolls, we get:

	[1, 2, 3] -> 1 time
	[1, 3, 2] -> 1 time
	[2, 1, 3] -> 1 time
	[2, 3, 1] -> 1 time
	[3, 2, 1] -> 1 time
	[3, 1, 2] -> 1 time

We end up getting exactly one instance of each possible permutation of the shuffled array, which means that Fisher-Yates produces random results with perfect uniformity. And that’s why Fisher-Yates is the gold standard when it comes to shuffling. It’s not so intuitive at first, but once we analyze all the possible permutations, it’s easier to see the difference between Fisher-Yates and our proposed naïve shuffling.