Shuffling Cards Fairly with the Fisher-Yates Algorithm

What a fair shuffle means

A fair shuffle is one in which every possible ordering of the deck is equally likely. A standard deck has 52 cards, so there are 52! orderings (factorials grow very quickly), which is about 8 x 10^67. A fair shuffle gives each of those the same chance, 1 in 52!.

That is a stricter standard than “looks mixed up”. A shuffle can produce results that look random to the eye and still favour some orderings over others. If you are simulating card games, a biased shuffle quietly distorts every probability you estimate from it.

The Fisher-Yates shuffle

The Fisher-Yates shuffle fixes this with a simple idea. Work through the list from the end. For each position, choose a random position from the start of the list up to and including the current one, and swap the two cards. Then move one position back and repeat.

In Python:

import random

def fisher_yates(cards):
    for i in range(len(cards) - 1, 0, -1):
        j = random.randint(0, i)      # 0 <= j <= i, both ends included
        cards[i], cards[j] = cards[j], cards[i]
    return cards

Think of it as filling the last position first. The last position can receive any of the n cards, with probability 1/n each. Whatever lands there is then fixed and left alone. The next position back can receive any of the remaining n - 1 cards, again with equal chance. Continue until the front. The number of equally likely sequences of choices is n x (n-1) x … x 1, which is n!, and each one leads to a different ordering.

That is the key: n! equally likely paths, n! possible orderings, and each ordering is reached by exactly one path.

A common biased version

A very natural-looking alternative swaps every position with a random position anywhere in the list:

def biased_shuffle(cards):
    n = len(cards)
    for i in range(n):
        j = random.randint(0, n - 1)  # any position at all
        cards[i], cards[j] = cards[j], cards[i]
    return cards

It looks reasonable, and it does mix the cards. But it is not fair, and you can see why with a short counting argument.

Why the naive version cannot be uniform

Take a list of just three cards. The naive loop makes three swaps, and each swap picks one of 3 positions. That gives 3 x 3 x 3 = 27 equally likely sequences of choices.

There are 3! = 6 possible orderings of three cards. If the shuffle were fair, each ordering would be reached by the same number of the 27 paths. But 27 divided by 6 is 4.5, which is not a whole number. So the 27 paths cannot be split evenly across the 6 orderings, and some orderings must come up more often than others.

In general, the naive method has n^n equally likely paths, while a fair shuffle needs the number of paths to be divisible by n!. For any list of three or more items, n^n is not divisible by n!, so the method is necessarily biased. Fisher-Yates avoids the problem because its path count is exactly n!.

Checking it with a simulation

You can see the effect by testing. Shuffle the three-item list [1, 2, 3] a large number of times, such as 60,000, and count how often each of the 6 orderings occurs. With a fair shuffle each ordering should appear about 10,000 times, give or take normal random variation of roughly a hundred. With the naive version, the counts typically separate into visibly different groups, with some orderings appearing noticeably more than 10,000 times and others fewer.

A frequency table or histogram of the counts makes the difference easy to see. This is a good use of simulation: the biased shuffle is hard to spot by looking at a few shuffled decks, but obvious when you count.

Other mistakes to watch for

• Off-by-one in the random range. In the correct version, j runs from 0 to i inclusive. If you choose j from 0 up to i - 1, the card can never stay where it is, and the result is again not uniform.
• Sorting by a random key done badly. Sorting with a comparison function that returns random results can be biased and may behave unpredictably. Assigning each card an independent random number and sorting by those numbers is fine, provided ties are very unlikely.
• Too few seeds. A shuffle is only as fair as the pseudo-random generators beneath it. If the generator is started from a small seed, it can only reach a tiny fraction of the 52! orderings, however correct the algorithm.
• Doing too little. A few swaps on a long list does not mix it.

In practice, most languages provide a tested shuffle function, and Python’s random.shuffle implements this method. It is generally best to use that rather than writing your own, and to write the algorithm yourself only to learn how it works.

Why it matters for simulations

Any simulation involving cards depends on the shuffle. Probabilities of drawing specific cards or hands assume that every ordering of the deck is equally likely. If the shuffle is biased, simulated frequencies drift away from the exact values, and you may wrongly conclude your hand calculation was mistaken. When a simulation disagrees with a calculation, the shuffle is a sensible early suspect.

Real physical shuffling is a separate matter, and how well a person mixes a deck by hand depends on how they do it. For this site’s purposes, the point is that each shuffle is independent: the order from an earlier shuffle does not change the odds for the next, and casino games carry a house edge no matter how fairly the cards are mixed. Gambling can be harmful, and support is available from local services for anyone who needs it.