The Perfect Shuffle
In class last week, we created a model of a deck of cards in ruby. I’m sure this has been done many times for all the online card games out there, but I wanted to play around with the functionality of the deck of cards, specifically, I wanted to create a perfect shuffle method.
A perfect shuffle (technically, a faro out-shuffle), is where you split the deck of cards exactly in half (26 cards in each stack), and then perfectly alternate cards when you shuffle. This leaves the top and bottom cards in place. (A faro in-shuffle is when the top card moves to second-from-top, and the bottom card moves to second-from-bottom).
This is an old (and very difficult) slight of hand, and it is useful to magicians because if you can do 8 faro out-shuffles, the deck returns to its original order.
So how did I implement this in ruby? Well, I have a card class that looks like this:
And a deck class that looks like this:
Notice that I have a shuffle method for a random shuffle, which is programmatically interesting in itself, and I’m curious if there is a cleaner way to do this. Here is the logic of my random shuffle method:
- Create an empty array to hold the new shuffled deck.
- Pick the first card of the current deck.
- pick a random number from 1 to 52 (well…okay, 0 to 51)
- if that slot in the shuffled_cards array is empty, insert the current card into that slot.
- if that slot is already occupied, pick another random number and try again.
- repeat steps a-c until an empty slot is found where I can insert that card.
- Repeat step 2 for each of the 52 cards.
This method is rather inefficient. For example, once I have 51 cards placed into the new shuffled deck, only one card remains, and there is only one slot for it go. It should take almost no computation at all to just insert the last card in the remaining empty slot. However, the computer will keep generating random numbers from 0..51 until it finds that empty slot, then it will insert the card. Theoretically, that number could never be picked, and it would be in an infinite loop. And even when it does pick the right slot, there is still a lot more computation going on than necessary.
What I need is an efficient algorithm to generate a random permutation of the numbers 0..51, which I can then use to just insert my current cards into the new deck in that random order. Any thoughts or idea or links or code snippets are welcome!
The Perfect Shuffle.
Let’s think about what a perfect shuffle is. Lets say my deck starts out sorted (where the suit order is spades, diamonds, clubs, hearts). Number the cards from 0 to 51 s.t.*
A♠ => 0
2♠ => 1
Q♥ => 50
K♥ => 51
A perfect shuffle will take the top half (cards 0..25) and the bottom half (cards 26..51) and alternate them in the following order:
So the new order of card will be:
Here is my implementation of the faro shuffle:
It may not be the cleanest method, but it works. I do wonder if there is a way to do two simultaneous loops, instead of declaring b as a separate variable, then looping through values of a. Something like the python implementation on the wikipedia page linked to above:
Is there something like this in ruby? maybe
* s.t. is a mathematical abbreviation for such that