Magic of Perfect Shuffles

In one card trick, the magician pulls out a new deck of cards and asks for a volunteer from the audience, whose name turns out to be Susan. She shuffles the deck several times, chooses one card, then shows it to the other spectators. She reassembles the deck and hands it back to the magician. The magician shuffles the cards several times, and the tells Susan that her card is the fifth card from the top. How did he do this magic trick?

In this assignmnet you will discover the mathematics of the perfect shuffle.

Credit to Ivars Peterson MAA Online

- Review basic Java concepts
- Reinforce the concept of object-oriented programming;

You are to implement a Java class

public class PerfectShuffle

initial deck: 0 1 2 3 4 5 6 7 shuffled deck: 4 0 5 1 6 2 7 3

Shuffles Deck Order 0 0, 1, 2, 3, 4, 5, 6, 7 1 4, 0, 5, 1, 6, 2, 7, 3 2 6, 4, 2, 0, 7, 5, 3, 1 3 7, 6, 5, 4, 3, 2, 1, 0 4 3, 7, 2, 6, 1, 5, 0, 4 5 1, 3, 5, 7, 0, 2, 4, 6 6 0, 1, 2, 3, 4, 5, 6, 7

Thus six in-shuffles are required to bring the cards back into their original sorted order.

Similarly, we introduce an ** out-shuffle** - in which we
interleave
cards starting with the top part. Here is an

initial deck: 0 1 2 3 4 5 6 7 shuffled deck: 0 4 1 5 2 6 3 7

Shuffles Deck Order 0 0, 1, 2, 3, 4, 5, 6, 7 1 0, 4, 1, 5, 2, 6, 3, 7 2 0, 2, 4, 6, 1, 3, 5, 7 3 0, 1, 2, 3, 4, 5, 6, 7

Thus three out-shuffles are required to bring the cards back into their original sorted order.

It turns out that an ordinary deck of 52 cards is returned to its original order after eight out-shuffles.

The ** PerfectShuffle** class must have the following class
members:

- only one instance variable
private int[] deck;

- a constructor for deck initialization (in sorted order) that accepts an input parameter for an original deck size
- a method
public int[] inShuffle(int[] input)

that performs a single in-shuffle on a given array of integers in a prescribed above fashion. The method does not change the input array.

- a method
public int[] outShuffle(int[] input)

that performs a single out-shuffle on a given array of integers in a prescribed above fashion. The method does not change the input array.

- methods
public int perfectInShuffle() public int perfectOutShuffle()

that returns the number of shuffles required to take the deck to its original state.

In this part we will discover the magician trick described in the lab preliminaries. As it turns out it's possible to move the top card of a deck to ANY location by using the right combination of in- and out-shuffles.

To move the top card to any position in the deck, express that position as a binary number. Starting from the left, perform a perfect shuffle for each digit in the binary number: an out-shuffle for 0 and an in-shuffle for 1.

For example, to move a card into position 14 (15th card from the top, since we count cards starting with 0), express 14 as a binary number: 1110. Three in-shuffles and one out-shuffle, in that order, bring the top card into position 14.

In the magician card trick, position 4 (5th card from the top) is 100 in binary, so the magician performs one in-shuffle, followed by two out-shuffles.

You are to implement a method

public int[] moveTopCard(int pos)

`deck`

) and moves the
top card into a specified position. The method returns a new deck and does
not change the original deck.
Hint. use `Integer.toBinaryString(pos)`

for converting an
integer to a binary string.

- PerfectShuffle.java

Your assignment will be graded first by compiling and testing it. After that, we will read your code to determine whether appropriate method/classes were used, as well as judge the overall style and modularity of your code. Points will be deducted for poor design decisions and un-commented, or un- readable code..

Here is the point breakdown:

- Part I - 60 points
- Part II - 20 points
- Coding style - 20 points.

Victor S.Adamchik, CMU, 2009