MrExcel.com - Your One Stop for Excel Tips & Solutions

Perfect Shuffle Challenge

A "perfect shuffle" is a trick used by card sharks and magicians to give the illusion of randomness when in fact the order of the cards is being controlled. It involves cutting the deck into two exactly equal halves, and then perfectly interlacing the two halves one card at a time.

For example, if the deck contains 52 cards numbers in order 1 to 52, the deck will be cut into a left half (numbered 1-26) and a right half (containing 27-52). They are merged, from the bottom up, starting with the bottom right card (52), then the bottom left card (26), then the next bottom right card (51), then card 25, 50, and so on. The deck will be in the order of 1, 27, 2, 28, ..., 25, 51, 26, 52.

Interesting fact: if you have a deck of 52 cards and repeat the perfect shuffle 7 more times, the deck will be back in the original starting order! So, for a deck of 52 cards, 8 perfect shuffles will leave the deck in the original order.

Challenge

Build an Excel workbook that will model a perfect shuffle for every even-size deck from 2 to 200 cards. What is the smallest number of perfect shuffles required to get the deck back in the original order?

For 4 cards, the answer is 2. For 52 cards, the answer is 8. What about the other deck sizes? Try to find the simplest and most elegant way of modelling this that you can. Try also to find interesting ways to display the answers and highlight any patters you may see emerging.

Bonus points if you can spot any pattern. Is there any way to model this for a deck size of 20,000 cards?

Prizes

Win a $99 bundle of Excel e-books.

Prizes Awarded For

  • Best Non-VBA solution
  • Best Solution
  • Most Interesting

Dates

April 24, 2013 through May 22, 2013.

Original Video Announcing The Contest

Results

The winners are:

  • Daniel Dion for the best non-VBA answer
  • Leo Meijer for most interesting
  • Alex Gordon for best VBA answer and overall best solution

Thanks to Dan Mayoh for proposing the challenge and for judging the competition.

Dan provided some notes about the entries:

Non VBA answers up to 200 cards:

A common way to model this problem for a deck size up to 200 was with a 200*200 array, with the first column being the order of the deck after 1 shuffle, the second column being the order of the deck after the second shuffle, and so on. Doing this involves two steps:

First is finding a formula that performs one ‘shuffle’, that is looks at the order of cards one column to the left, and rearranges it for the current column. This formula is then dragged across all columns. This was done in a few different ways. Most people (myself included) did this in a direct manner, using some sort of INDEX and OFFSET combination to pick up the correct number from the right spot in the previous deck. A couple of people used what I think is a very clever idea and first used some very simple functions to make a ‘reference column’, equal to the deck after 1 shuffle. Then, for all subsequent shuffles, they use a much simpler formula (no OFFSETS) that looks at the value of the reference column for a given row, and returns the card in that value’s place from the previous column. Alex Gordon’s entry was the best example of this.

Daniel Dion's formula to do the shuffle
Daniel Dion's formula to do the shuffle
Alex Gordon set up a reference column to do the shuffle
Alex Gordon set up a reference column to do the shuffle

In Alex's workbook, cell E6 contains =1+E4 and this is copied down. The formula in H4 is = INDEX(G$4:G$1003, $E4) * $C4 and is copied down and across.

The second step is to then check whether the current column matches the original starting order. If it does, you take note of how many shuffles this took to occur, and you’re done. The best way to do this is with a single array formula taking up just one cell above the column. Daniel Dion did this very well. Some people performed this step but checked only the location of the ‘2’ card, and deciding that when it is back in its original spot, the whole deck is in order. As it turns out, this will give the right answer, but a fair bit of mathematics is required to demonstrate that. And if the 2 card is all you are checking in this second step, then it is a waste of resources to model the shuffling of every card in the deck. A third approach to do this second step was to utilise a second worksheet with another 200*200 array, but this is far less efficient than an array formula.

Here is Alex Gordon's chart showing the number of shuffles required for different sized decks. There is not a particular pattern that is apparent.

Alex Gordon's chart showing the number of shuffles
Alex Gordon's chart showing the number of shuffles

Non VBA answers for large numbers of cards

An observant modeller may notice that tracking the location of the ‘2’ card seems to be sufficient for any deck size. When it is back in its starting spot, the whole deck appears to be. Indeed this is the case, and can be proven with some heavy mathematics. The modelling advantage of this is that we can use a 2*n array (2 columns and n rows) instead of a n*n array to solve the problem for large deck sizes of n. Each new location of the 2 card simply depends on the previous location and the deck size. A simple formula calculates this. This can then be practically modelled in Excel for deck sizes up to 50,000 without effort. Surprisingly, no one submitted a solution like this.

But what about a deck size of 20,000,000 without VBA? Can that be done?

VBA answers for large numbers of cards:

A few different approaches were submitted here, some in the form of sub-routines and some as UDFs. The fastest approaches submitted, which can calculate deck sizes up to 20,000,000 in less than a few seconds, would simply calculate the position of the 2 card after a shuffle, check if they should stop, perform another shuffle, and repeat. And really, tracking the 2 card is all that should be done in a VBA solution. For a problem like this, ‘small’ deck sizes can be well modelled without VBA. VBA is only needed for large deck sizes, and if used a premium should be put on speed and efficiency of the code. Some people used VBA to track every card in the deck, and would paste results in to an Excel worksheet. Whilst such a method gives the right answers, it is unworkable for large deck sizes. There was one particularly innovative VBA solution submitted by Leo Meijer. Everyone else in their VBA answers used a mathematical function to reposition the cards after a shuffle. Leo on the other hand literally coded a perfect interlace shuffle. He took an array containing the card values, split it at the halfway point in to two smaller arrays, and then populated a new array one card at a time by taking a card from the left array, a card from the right array, a card from the left array, a card from the right array, and so on. I really liked that idea!

Some final comments

I have been playing around with non-VBA answers for deck sizes in the 20,000,000 range. For a deck size d, the location of the ‘2’ card after s shuffles can be found directly by the formula =MOD(2^s,d-1)+1, without the need for interim results. There are two problems with this however. One is, it still involves trial and error to see what value of s makes this formula equate to 2. And two is Excel’s MOD function can’t cope once 2^s exceeds 2^55.

I was able to solve the second problem by essentially taking some interim MOD calculations that will never be larger than the square of the deck size. Hence if Excel’s limit for the first argument of the MOD function is 2^55, I can use this for deck sizes up to =SQRT(2^55) or about 190,000,000.

The first problem though, I still haven’t found an answer for without VBA. If you would like to check out Dan's workbook, see the nonvba verylarge worksheet in DanMayohPerfectShuffle.xlsm.

Download winning entries

If you would like to study the winning entries, they are here.