Ruby vs. Java in Solving The Perfect Shuffle Problem, Part 2 of 3

Prev: Introduction

The Perfect Shuffle Problem

The Perfect Shuffle Problem involves determining how many shuffles are required to return a deck of cards to its original order . The following is a formal definition from halfbaked.net.

Given a deck of nCards unique cards, cut the deck iCut cards from top and perform a perfect shuffle. A perfect shuffle begins by putting down the bottom card from the top portion of the deck followed by the bottom card from the bottom portion of the deck followed by the next card from the top portion, etc., alternating cards until one portion is used up. The remaining cards go on top. The problem is to find the number of perfect shuffles required to return the deck to its original order.

Your function should be declared as:

static long shuffles(int nCards,int iCut);

What is the result of shuffles(1002,101)?

We need to conceptualize what we are going to solve, and we are not going to do that thinking about a 1002 card deck and a 101 card cut. Most of us are familiar with a 52 card deck. But even shuffling 52 cards is difficult to visualize. So, let’s first investigate how many perfect shuffles are required to bring a 6 card deck with a 2 card cut to its original order.

The initial position of the cards is shown in the following image. I number the cards 1 through 6. I also number the position of the cards, 1 through 6. So the original position of cards 1 – 6 is positions 1 – 6 respectively.

If we perform a two card cut, we end up with two stacks of cards. One stack contains cards 1 and 2, and the other contains 3 – 6. Performing a perfect shuffle on these yields the descending card order 3, 4, 1, 5, 2, 6. Another perfect shuffle brings us 1, 5, 3, 2, 4, 6.

The third perfect shuffle renders 3, 2, 1, 4, 5, 6. The fourth 1, 4, 3, 5, 2, 6.

The fifth shuffle leads to the order 3, 5, 1, 2, 4, 6. Finally, the sixth shuffle returns the cards to their original positions.

Brute Force Solution

So six cards with a cut of two cards needs six shuffles? Not too bad. At this point you may be tempted simply use a brute force implementation.

The pseudo-code for the brute force implementation is straightforward.

1. Initialize each card Ci in deck D to position i.

2. Shuffle deck D.

3.Until each card Ci is in its original position i:
increment shuffle count,
shuffle again (2).

Such a method works fine for six shuffles. However, if you try to use brute force to solve 1001 cards with a cut of 101, which I encourage you to do, you will quickly find it doesn’t work. Or well, you’ll slowly find it doesn’t work — it takes too long. Your brute force program will need to shuffle the deck 5,812,104,600 times! With each shuffle your program manipulates and investigates an array of 1001 elements. So, the brute force solution is of the order C × S, where C is the number of cards in the deck, and S is the number of shuffles required. We need to improve upon C × S.

There is no way to reduce C. In other words, there is no magic formula to determine where a card will be after shuffling it, without shuffling it. There is a way to improve upon S however.

Cycle Based Solution

Understanding the improved solution requires that we observe the way each card shuffles within the deck. Look at what happens to card 1 during the first two shuffles in the example above.

The first obvious conclusion is that card 1 returns to position 1 after the second shuffle. The second conclusion is less obvious but key to improving upon the brute force algorithm: any card in position 3 will return to it’s original position after two shuffles as well. That’s because card 1 passes through position 3, and shuffling by definition is the exchange of one card’s position with another. Looking at the image again, we see that card 3 is indeed back at it’s original position after two shuffles

For a slightly more complicated example, look at card 2 above. It visits position 5, then 4, then returns to position 2 on the third shuffle. Given the cyclical nature of shuffling we expect cards 5 and 4 to return to their initial locations after three shuffles as well. Indeed they do.

We have looked at cards 1 – 5. The final card, 6 remains in place throughout. In other words, it is at its original position after only one shuffle.

So, some of the cards require two perfect shuffles, some require three, and one card requires one. To determine the number of shuffles required for the entire deck, we simply find the lowest common multiple of these, which is six.

Now we have a way to determine the number of perfect shuffles required by examining the deck on a card by card basis. We need to look at each card position once, and only once. The pseudocode is below.

1. Intialize each card Ci in deck D to position i.

2. Until Ci is in position i:
shuffle Ci to new position j,
increase shuffle count,
mark j as visited.

3. Record the shuffle count at all visited positions.

4. Repeat shuffle process (2) for the next Ci
where i has not been visited.

5. When we have visited each position:
calculate total perfect shuffles required which is
the lowest common multiple of shuffles required for every Ci.

Again, this new algorithm requires that each position in the deck needs to be investigated only once. We need to shuffle the deck C times and therefore our new order of complexity is simply C, a major improvement.

But we need to implement our algorithm. In the next post I’ll provide both Java and Ruby code to do just that.

Next: The Code