Due 10/6

This exercise, together with HW08, is about card shuffling. You will be implementing an algorithm that generates all possible orderings of a desk of n cards after shuffling k times.

You may have noticed that shuffling only once does not produce all possible orderings of a deck of cards. For example, if the original deck has 4 cards, the number of all possible orderings is 24. However, shuffling a deck of cards once will give us only 14 orderings, not 24. Moreover, some of the 14 results are the same. Note that 24 is 4!, and 14 is $2^4$ - 2. If we are dealing with 5 cards, there are 5! possible orderings, but shuffling once will give us only ($2^5$ - 2) orderings (with repetitions).

Algorithm

Step 1

For a deck of n cards, divide it into two decks (upper deck and lower deck). Each deck has at least one card. The orders inside each deck is not changed. For example, if the original deck is 2345678 (each number is a card, 2 is at the top and 8 is at the bottom).

• One possible result is upper: 23 lower: 45678
• Another possible result is upper: 234 lower: 5678
• Yet another possible result is upper: 2345 lower: 678

Step 2

Interleave the two decks. Please be careful that the orders in the upper deck and the lower deck are unchanged. For example, if the upper deck is 234, in the newly shuffled deck, 2 is still above 3 and 3 is still above 4. Similar, if the lower deck is 5678, in the newly shuffled deck, 5 is still above 6 and 6 is still above 7. The order of the cards in the two decks may interleave. The following are some possible results:

1. 2 is between 5 and 6; 3 is between 6 and 7
2. 23 are between 5 and 6
3. 234 are all between 5 and 6
4. 234 are all above 5 (thus, the new deck is the same as the original deck)

There are other possible results.

Step 3 – combining the first two steps

Suppose the original deck is 234. The are two ways to divide it into an upper deck and a lower deck:

1. upper: 2 lower: 34 or
2. upper: 23 lower: 4

Interleaving them can produce these results:

1. upper: 2 lower: 34
   234 (2 above 3 and 4),
   324 (2 between 3 and 4),
   342 (2 below 3 and 4),
or
2. upper: 23 lower: 4
   423 (4 above 2 and 3),
   243 (4 between 2 and 3),
   234 (4 below 2 and 3)

Please notice that 432 cannot appear.

Getting started

Run 264get hw07 to get the code. You will be implementing the functions described under Requirements below.

Output format

You will use print_deck(…) (declared in utility.h) to produce the output. The format is illustrated below. Note that these results are possible orderings of the deck "[6789A23]". Please read the outputs from top to bottom, left to right.

[6789A23] [678A923] [67A8923] [6A78923] [A678923] [678A293] [67A8293] [6A78293] [A678293] [67A2893] [6A72893]

[A672893] [6A27893] [A627893] [A267893] [678A239] [67A8239] [6A78239] [A678239] [67A2839] [6A72839] [A672839]

[6A27839] [A627839] [A267839] [67A2389] [6A72389] [A672389] [6A27389] [A627389] [A267389] [6A23789] [A623789] [A263789] [A236789]

How many possible orderings can the new deck have?

If there are k cards in the original deck, there are k - 1 different ways to divide the original deck to two decks:

1. the upper deck has 1 card, the lower deck has k - 1 cards
2. the upper deck has 2 cards, the lower deck has k - 2 cards
3. the upper deck has 3 cards, the lower deck has k - 3 cards
4. the upper deck has 4 cards, the lower deck has k - 4 cards
   ...
   k-1. the upper deck has k - 1 cards, the lower deck has 1 card

If the upper deck has n cards and the lower deck has m cards, there are $\frac{(n+m)!}{n!m!}$ ways to interleave the two decks, while keeping the orders in the original upper deck and the original lower deck.

If the original deck has k cards (i.e., n + m is k), there are totally $\frac{k!}{1!(k-1)!} + \frac{k!}{2!(k-2)!}+ ... + \frac{k!}{(k-1)!1!}$ results, as the upper deck may have 1, 2, 3, ..., k - 1 cards. (Remember that both n and m must be one or larger.) This happens to be parts of the binomial expansion: $(x+y)^k = \sum_{n=0}^{k} \frac{k!}{n!(k-n)!}x^ny^{k-n}$
If the first and the last terms are removed, it becomes $\frac{k!}{1!(k-1)!} + \frac{k!}{2!(k-2)!}+ ... + \frac{k!}{(k-1)!1!}$

Please be aware that if a new deck appears multiple times, it is counted multiple time. In the previous example, 234 is counted twice.

For a deck of k distinct cards, there are k! possible orders (i.e., permutations).

$k$		2	3	4	5	6
$k!$		2	6	24	120	720
$2^{k}-2$		2	6	14	30	62

As you can see, $2^k - 2$ is equal to $k!$ when k is 2 or 3 and smaller than $k!$ when k is 4 or larger. Thus, shuffling once cannot generate all possible orders, except for only k is 2. Actually, $2^k - 2$ counts the same output multiple times; in the previous example, 234 is counted twice and 432 is not generated. For simplicity, ECE 264 does not ask you to determine which orders are missing.

divide(…)

This program find the possible outcomes of dividing a deck of cards into a pair of upper and lower decks. The division is done such that if the upper deck is placed above the lower deck, you get back the original deck. After dividing the cards into the upper and the lower decks, they are interleaved into a single deck (using the interleave(…)). This is called one round of shuffling.

You have to implement a function to find and store all possible pairings of non-empty upper and lower decks in two arrays.

The divide(…) function has three arguments: orig_deck is the original deck of cards upper_deck and lower_deck are two arrays with sufficient amounts of memory upper_deck[i] and lower_deck[i] form a pair. The caller of divide (shuffle(…)) should allocate enough memory for upper_deck and lower_deck before calling divide(…).

shuffle(…)

You also have to implement a function to perform the shuffling. In this shuffling function, you have to call the division function to get all possible pairings. Before you call the division function, you have to allocate sufficient space such that all possible pairings can be stored. For each pair of upper and lower decks, you have to perform interleaving. You have to deallocate or free the space storing the pairings before you exit from the function.

You are allowed to have additional functions in the file. The output for up to five cards are provided for reference. Please understand that when your submission is graded, the input deck may not include cards 'A', '2', ... Your program must use what is given to the function, without assuming what cards are in the original deck.

Requirements

Submit

To submit HW07, type 264submit HW07 shuffle.c from inside your hw07 directory.

Pre-tester ●

The pre-tester for HW07 has been released and is ready to use.

Q&A

Answers to common questions may be posted here later.

Updates

9/25/2017

Draft.