The Perfect Shuffle

A perfect shuffle occurs when you shuffle a deck of cards so that all the cards from the second half of the deck are perfectly interspliced between the cards in the first half of a deck. Such a shuffle is illustrated in Figure 1.

Figure 1. A perfect shuffle takes the second half of the deck and inserts it evenly into the first half.

If you continue to shuffle cards in this manner, eventually the original order returns, shown in Figure 2.

Figure 2. For an 8-card deck, only three perfect shuffles are required to restore the original order.

Mathematically, you can determine how many perfect shuffles are required to return to the original order based on the number of cards in a deck. Surprisingly, the number of shuffles doesn’t increase proportional to the deck size. I’ll leave that quandary for the eggheads to figure out. For this month’s Exercise, your job is to implement a perfect shuffle function.

Use your perfect shuffle function on a char array representing the 26 letters of the Latin alphabet:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Count the number of perfect shuffles it takes to restore alphabetical order to the string.

Click here to view my solution, but please first try this Exercise on your own.

Leave a Reply