How Computers Shuffle - Explained with Cards and Dice

Introduction

This is meant as a hands-on way of looking at different shuffling methods and the steps a computer takes to do them. It is meant as a way of introducing the ideas of algorithmic efficiency without talking about Big O notation. For more detail about the performance of these algorithms, or for further reading, I suggest Mike Bostock's blog post on the Fisher-Yates Shuffle.

Materials

• 6 different cards
• Paper with 1 to 6 written on it
• Dice
• Paddle pop stick

You can see the materials I used in the header image for this post.

Note on Dice Rolls: At times we don't want to roll a number between 1 and 6. Instead we want a number between 1 and something less than 6. To do this, we can roll the dice and ignore results that we don't want and instead roll the dice again. Alternatively, you can do what I did and make 5, 4, 3, 2 and 1 sided dice by putting crosses on the excess sides.

How Do Humans Shuffle

There are several techniques that people use to shuffle. Two techniques that you may have seen or used are smooshing and the overhand shuffle.

Smooshing - spread all of the cards out on the table and move them around pushing them into each other. Keep mixing them for a minute. Gather them up into a single pile.

Overhand Shuffle - Hold all the cards in one hand, grab some and then drop them back into the deck. Keep doing this until you're ready.

Numberphile has a great video on different shuffling techniques and how long you need to shuffle for to ensure that the deck is in a random order.

How Can Computers Shuffle

Computers don't have hands that they can use, or physical cards to move around. So how can they shuffle?

Lazy Naive Shuffle

Process:

1. Start with a deck of cards laid out and an empty deck to put the shuffled cards into.
2. Roll a six sided dice
3. Check if the card has already been shuffled
4. If it hasn't, move it to the shuffled pile
5. Repeat until no cards are left to be shuffled

Lazy Naive Shuffle Questions:

1. How many times did you need to roll the dice?
2. What happens if you never roll a six?
3. What would happen if you were shuffling a deck of 52 cards? How many times would you roll a number that had already been shuffled?

Better Naive Shuffle

Process:

1. Start with a deck of cards laid out and an empty deck to put the shuffled cards into.
2. Roll an n-sided dice (n is how many cards are left to be shuffled)
3. Move the card in that position to the shuffled pile
4. Move cards left one at a time to fill in the now empty space
5. Repeat until all cards are shuffled

Better Naive Shuffle Questions:

1. How many times did you need to roll the dice? Why was this?
2. What would happen if you were shuffling a deck of 52 cards? How many cards would you need to move if you rolled a 1?
3. What are the advantages of this approach over the Lazy Naive Shuffle? What are the disadvantages?

Fisher-Yates Shuffle

Process:

1. Start with a deck of cards laid out with a marker at the end to show which cards have been shuffled.
2. Roll an n-sided dice (n is how many cards are left to be shuffled)
3. Swap the card in that position with the last unshuffled card
4. Move the shuffled marker forwards one space
5. Repeat until no cards are left to be shuffled

Fisher-Yates Shuffle Questions:

1. How many times did you need to roll the dice? Why was this?
2. What would happen if you were shuffling a deck of 52 cards? How many times would you need to move cards if you rolled a 1?
3. Is this still shuffling because you are swapping cards instead of moving them to a new deck?

Answers/Discussion Ideas

Lazy Naive Shuffle:

1. You likely needed to roll the dice more than six times, unless you got really lucky.
2. If you never roll a six, you will never shuffle all of the cards. The same happens if you only ever roll a six. These situations are unlikely, but possible.
3. After half the cards (26 cards) have been shuffled, there is a 50% chance of rolling a number that has already been shuffled. Shuffling more cards gives you more chances to roll the same number twice making shuffling slower the more cards you start with.

Better Naive Shuffle:

1. You only needed to roll the dice six times. You could do this because now instead of rolling to fill a space, you would move the cards to fill the space.
2. If you rolled a 1, you would need to move every single unshuffled card forward one space before rolling again. You end up needing to move most of the cards several times while shuffling. If you only ever rolled a 1, then you need to move the last card 52 times, the card before it 51, then 50 and so on.
3. This approach is better as you only need to roll once for each card. It is worse because now you need to move cards multiple times.

Fisher-Yates Shuffle:

1. You only needed to roll the dice six times. You could do this because you were always rolling top pick one of the unshuffled cards.
2. If you rolled a 1, you would only need to swap the first card with the last unshuffled card. This means that for a deck of 52 cards, you only swap/move cards 52 times.
3. This is still shuffling. Every time you roll the dice there is an equal chance that one of the unshuffled cards will be picked and moved. They do not need to stay in the order they started in and they do not need to start in order. See the below for an example of items being shuffled that have no clear order.