Python Application: Simulating a Perfect Shuffle

# Python Application: Simulating a Perfect Shuffle

People learning to program often struggle with how to decompose a problem into the steps necessary to write a program to solve that problem. This is one of a series of posts in which I take a problem and go through my decision-making process that leads to a program.

Background: I once attended a presentation by an amateur magician in which he stated that performing 8 perfect shuffles in a row on a deck of 52 cards returned the deck to the original order. A perfect shuffle is where you divide the deck into two, evenly sized stacks and when merging the stacks you are able to do so such that every other card comes from the same stack.

Problem: Write a program to determine if 8 perfect shuffles in a row return a deck of 52 cards to the original order. I assume that you understand statements, conditionals, loops, lists, and functions. Below I create two versions of the program. The first is very explicit and doesn’t take advantage of many Python features.

You can find a video with more details at https://www.youtube.com/watch?v=-pNfKbdsFog.

Design:

I start by thinking how to represent the cards. The claim above simply states that for whatever order the deck of cards is initially in, after 8 perfect shuffles it will return to its original order. It says nothing about the suits and values of the cards, so we don’t need to keep track of this information. Therefore, I will use an list consisting of the integers 1 to 52 as my cards. In the discussion below, this list is “cards”.

Each time I shuffle, I need to simulate dividing the deck into two stacks of 26 cards each followed by merging them such that one card comes from each stack during the merging. That is, when merging I get the first card from stack #1, the first card from stack #2, the second card from stack #1, the second card from stack #2, and so forth.

Representing the two smaller stacks is simple–the “left” stack will consist of the first 26 cards from the deck and the “right” stack will consist of the last 26 cards. That is

```left[0] = cards[0]
left[1] = cards[1]
.
.
.
left[25] = cards[25]
```

with a pattern of

```left[i]= cards[i]
```

For producing the “right” stack, we can see that

```right[0] = cards[26]
right[1] = cards[27]
.
.
.
right[25] = cards[51]
```

with a pattern of

```right[i] = cards[i + 26]
```

Merging is more of a challenge. I will print the current state of the loop after each shuffle and don’t care about the order before that, so I can re-use “cards” when merging. As for the merged values, cards[0] = left[0], cards[1] = right[0], cards[2] = left[1], cards[3] – right[1], and so forth. I can see that the indices of “cards” increments by one each time, but I use “left” and right” in pairs with the same index. That is, I use left[0] and right[0], then left[1] and right[1], and so on. This means that I need one indexing variable for “cards” and another for “left” and “right” so that I can increment them by different step sizes (for this approach).

Final Program, version 1:

```def shuffle( c ) :
left  = [ ]
right = [ ]

for i in range(0, 26) :
left.append(c[i])
right.append(c[i+26])

i = 0
k = 0
while i < 52 :
c[i]   = left[k]
c[i+1] = right[k]
i += 2
k += 1

########  main  ########
cards = []

for i in range(0, 52) :
cards.append(i+1)

print("original deck")
print(cards)

for i in range(0, 8) :
shuffle(cards)
print("\nshuffle # %d" % (i+1))
print(cards)
```

The design given above lends itself more to the first implementation, which is how you might do it in some other programming languages. However, we may wish to take advantage of Python’s language features that make some things easier. I can use slicing to produce the two subsets of the deck, resulting in two new lists.

When merging I can use slicing again, both on the left and right sides of the assignment operator. This includes using a step size other than 1. When merging, I want to make the following changes to “cards”: cards[0] = left[0], cards[2] = left[1], cards[4] = left[2], and so forth. Similar changes need to be made to “cards” at indices 1, 3, 5, … This can be performed with slicing.

Final Program, version 2:

```def shuffle( c ) :
left  = c[  :26]  # slice from beginning to index 25
right = c[26:  ]  # slice from index 26 to end

c[0: :2] = left[ : ]   # replace every other value of
#   c starting at index 0
c[1: :2] = right[ : ]  # replace every other value of
#   c starting at index 1

########  main  ########
# create list using list comprehension
cards = [ n for n in range(1, 52+1) ]

print("original deck")
print(cards)

for i in range(0, 8) :
shuffle(cards)
print("\nshuffle # %d" % (i+1))
print(cards)
```