The Fisher-Yates Shuffle is named after statisticians Ronald Fisher and Frank Yates, who developed the original algorithm in 1938. In 1964, Richard Durstenfeld developed a more modern version of the algorithm which improved upon its asymptotic complexity and was optimized for use with computers. Donald Knuth published this modernized version of the Fisher-Yates Shuffle in his 1968 book, The Art of Computer Programming. For this reason, the Fisher-Yates Shuffle is also known as the Knuth Shuffle.
This article is about the modernized Fisher-Yates Shuffle.
What Does it Do?
The purpose of the algorithm is to randomly shuffle a collection in place. The Fisher-Yates Shuffle is great for when you need to produce an unbiased result; a truly random permutation of some collection.
The basics are as follows:
- Begin with a list of items that we want to shuffle randomly.
- Choose, at random, one of the unshuffled items. (Not an item that has already been shuffled).
- Swap this chosen item with the last item in the list that has not already been selected.
- Repeat the previous two steps, moving back-to-front through the list, until all items have been shuffled.
Note that in the above description, the algorithm moves through the list from back-to-front. This is a convention, but it is how you will see most implementations of the algorithm online. This approach can also be implemented from front-to-back; an example of that is shown under the ‘Implementation’ heading of this article.
Check out the visual representations under the ‘Step-by-Step’ heading for an example, and a better understanding of how the algorithm works.
It is important to understand that this algorithm modifies the list in-place. No copy of the list is made. The Fisher-Yates Shuffle is a destructive algorithm; it permanently mutates the list it is working on.
What Doesn’t Work?
There are some approaches to shuffling a list which may appear to be random but actually are not. An approach that may seem uniform at first glance is to iterate through the list and swap each element with any random element. The problem is that in order to achieve a truly uniform shuffle, we cannot just choose any random element from the list. We must exclude elements at indexes that have already been visited/shuffled.
How do we know that an approach is truly random? The modulus resulting from the possible combinations of choices divided by the number of outcomes available should be 0. If the possible choices are not evenly divisible by the available outcomes, then each outcome does not have an equal chance of occurring. This written explanation may be difficult to parse, so let’s look at a visual example.
import itertoolsmy_list = ['c', 'a', 't']# possible outcomes
=> [('c', 'a', 't'), ('c', 't', 'a'), ('a', 'c', 't'), ('a', 't', 'c'), ('t', 'c', 'a'), ('t', 'a', 'c')]
We can see there are are six available outcomes (possible permutations) for shuffling our list,
Now that we know the number of possible outcomes, we need to know the number of possible combinations of choices. When shuffling our list with the simplistic approach above (choosing any random element from the list to swap with), we would have three random indexes to choose from at each element as we iterate through the list — 0, 1, or 2. Multiplying these choices together,
# amount of possible choices
3³ = 27.
Let’s get the modulus of our possible choices and our available outcomes.
27 % 6 = 3
We can see that each of our outcomes does not have an equal chance of occurring.
Now let’s see how the math works out for our more sophisticated approach, the Fisher-Yates Shuffle. Our number of possible outcomes is the same. But the way we choose a random index to swap with differs. The Fisher-Yates Shuffle dictates that we only choose from the current index and all other indexes that have not yet been visited. This means that for our three-element example list we first have three possible indexes to choose from (0, 1, 2), then two (0, 1), then one (0). We can calculate the amount of possible choices as the factorial of our list’s size:
# amount of possible choices
3! = 6
Now we see that the modulus of our possible choices by our potential outcomes is equal to zero, meaning it divides evenly. In this case the two numbers are actually the same, but that will not always be the case.
6 % 6 = 0
Achieving True Randomness
Let’s reiterate the most important traits of the Fisher-Yates Shuffle that ensure it is truly random. We touched on these in our above example.
A crucial trait of a truly random shuffle is that each item in the collection must have an equal probability of being placed in any position in the resulting list — including its original position. If an item is less likely to end up in its original position than any other position in the list, then the shuffle is not truly uniform. When we choose a random index with which to swap values (my implementation handles this with a helper function), the current index should be included as a possible return value.
Additionally, each position in the list should only be considered for a random swap of its value one time. This means that that once an element has been placed in its new position, we no longer consider that position in the shuffle. Let n be the size of the list to be shuffled. As we move through the list back-to-front, we first swap a random index’s value into the last index of the list, (n — 1). After doing so, we move forward to index n — 2. At this time we again need to choose a random index with which to swap values. However we must exclude n — 1 from the possible random positions with which to swap. Once an item has been “placed” at an index already visited, it cannot be moved.
Let’s again use a very small example list:
my_list = [‘c’, ‘a’, ‘t’]
Below you can see each element of the list in its original order, with the index listed underneath.
We will follow convention and begin at the last index of the list, 2. Recall that we must include the current index position in the range of possible random swap locations.
random_int(0, 2) # helper returns a random val between 0 and 2
Let’s say our randomly chosen position with which to swap values is 0.
We now move forward in the list to index 1. At this point, we must not consider index 2 as a possible position to swap with.
Finally, we reach the first index of our list, 0. Because we have no index positions left to swap with, we can end here.
list is now permanently mutated to its now randomly shuffled order.
=> ['a', 't', 'c']
In this brief example, no element was ‘swapped’ with itself. However, it is a key attribute of the Fisher-Yates Shuffle that this can and does happen.
Here is an example of the Fisher-Yates Shuffle implemented in Python. This first example is written to iterate through the list back-to-front, following convention. You will most often see the algorithm written this way.
Below in a second example is a very similar implementation that works its way through the list front-to-back. Both work.
The modern version of the Fisher-Yates Shuffle uses constant space — O(1) — because we are shuffling the list in place. We do not create a copy of the list as part of the shuffling process.
The time complexity of the algorithm is O(n), with n representing the size of the list we are shuffling. We know the time complexity is linear, O(n), because the algorithm iterates through each element of the list. This is an optimization over the original Fisher-Yates Shuffle, which had a time complexity of O(n²).
Below are some of the sources I found useful while reading up on the Fisher-Yates Shuffle and writing this article. If you’re interested in reading more about the algorithm, check them out.