Card shuffling #1 (E)
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
(each number is a card, is at the top and is at the bottom). One possible result is upper: lower:
 Another possible result is upper: lower:
 Yet another possible result is upper: lower:
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
, in the newly shuffled deck, is still above and is still above . Similar, if the lower deck is , in the newly shuffled deck, is still above and is still above . The order of the cards in the two decks may interleave. The following are some possible results: is between and ; is between and
 are between and
 are all between and
 are all above (thus, the new deck is the same as the original deck)
Step 3 – combining the first two steps
Suppose the original deck is . The are two ways to divide it into an upper deck and a lower deck: upper: lower: or
 upper: lower:
 upper:
( above and ),
( between and ),
( below and ),
or
lower:  upper:
( above and ),
( between and ),
( below and )
lower:
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:
 the upper deck has 1 card, the lower deck has k  1 cards
 the upper deck has 2 cards, the lower deck has k  2 cards
 the upper deck has 3 cards, the lower deck has k  3 cards
 the upper deck has 4 cards, the lower deck has k  4 cards
...
k1. 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!(k1)!} + \frac{k!}{2!(k2)!}+ ... + \frac{k!}{(k1)!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!(kn)!}x^ny^{kn}$
If the first and the last terms are removed, it becomes
$\frac{k!}{1!(k1)!} + \frac{k!}{2!(k2)!}+ ... + \frac{k!}{(k1)!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,
is counted twice and 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 nonempty 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
 Your submission must contain each of the following files, as specified:
file contents shuffle.c functions interleave(CardDeck upper deck, CardDeck lower deck)
→ return type: voidPrint all possible interleavings of upper_deck with lower_deck. Use
print_deck(…)
to print each resulting order.  Do not make assumptions about the order or composition of the original deck. For example, may come before or after , or may not be present at all.
print_deck(…)
and MAX_SIZE are declared in utility.h. Tip: There should be no uncertainty in this function. If you think a random number generator is needed, you are on the wrong track.
 Tip: To copy the elements of one array from one array to another (e.g., the array of cards in a
CardDeck
), you could usememcpy(…)
. The=
operator will simply copy the address, not the elements themselves.  ⚠ You must use MAX_SIZE for the maximum length of a deck. Do not use 13.
 ⚠ Any memory allocated with
malloc(…)
must be freed. There are penalties for memory leaks.
divide(CardDeck orig deck, CardDeck ✶ upper decks, CardDeck ✶ lower decks)
→ return type: voidDivide a deck into into pairs of upper and lower decks. upper_decks and lower_decks are arrays of CardDeck. (i.e., Each element is a CardDeck.)
 Assume upper_decks and lower_decks are allocated before
divide(…)
is called. 
If the original deck has n cards, there should be n  1 pairs of upper and low decks:
 upper deck has 1 card, low deck has n  1 cards
 upper deck has 2 cards, low deck has n  2 cards
 upper deck has 3 cards, low deck has n  3 cards
...
n1. upper deck has n  1 cards, low deck has 1 cards
 upper_deck[i] should contain the first i+1 cards from
orig_deck. For example:
 upper_deck[0] should store the first card in the original deck.
 upper_deck[1] should store the top two cards in the original deck.
 upper_deck[2] should store the top three cards in the original deck.
 Tip: Remember that within
CardDeck
, cards should be an array ()  ⚠ Do not call
malloc(…)
in this function.
shuffle(CardDeck orig deck)
→ return type: voidGenerate all possible decks that could result from one shuffle. orig_deck contains the number of cards.
 The number of upperlow deck pairs should be the number of cards  1.

Follow these steps:
 Calculate the number of upperlow deck pairs.
 Allocate enough memory to accommodate the pairs.
 Call
divide(…)
to find these pairs.  For each pair of upperlower deck, call
interleave(…)
to interleave the cards.  Release the allocated memory.
 The amount of memory allocated in this function must be determined based on the size of the original deck. The program may fail if the allocated memory has a fixed size (some students like to use 1000 but nobody could explain why 1000).
 ⚠ A penalty of 50% of the possible points will be deducted if the amount of allocated memory is not determined by the size of the original deck, e.g., if you use 100, 1000, 10000, or any other fixed number.
 Use
 Your program must output the same lines as any other correct solution. However, the order may be different.
 Do not print anything other than the required output (i.e., no debugging output, etc.).
 Submissions must meet the code quality standards and the course policies on homework and academic integrity.
Submit
To submit HW07, type
264submit HW07 shuffle.c
from inside your hw07 directory.
Pretester ●
The pretester 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. 