Card shuffling #2 (A)
Performing k rounds of shuffling
In HW07, your program gets a deck of cards and shuffle this deck once. The program prints the possible orders (with repetitions) after one round of shuffling. 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).
This assignment extends the exercise to print the possible orderings of a deck after k rounds of shuffling, using the function
void repeat_shuffle (CardDeck orig_deck, int k);
where the first parameter is the original deck (orig_deck) and the second parameter is the number of rounds of shuffling to be performed. We assume that a round of shuffling is always performed on a complete deck of cards. It involves dividing a deck of cards into non-empty upper and lower decks, and interleaving the two decks into a complete deck again. The next round of shuffling, if any, should be performed on the complete (shuffled) deck, and the process continues until all k rounds of shuffling have been performed.
The sample output for a deckshuffled 3 times is given as a reference. Shuffling once produces 14 (= $2^4$ - 2) lines. For each of these orderings, we perform another shuffling to produce 14 possible orderings (with repetitions). Therefore, the second round of shuffling will produce 14*14 possible orderings (with repetitions). Consequently, shuffling 3 times produces 2744 (14*14*14) lines altogether. It is acceptable that the possible orderings produced by your program do not match the order in which the possible orderings appear in the listing produced by the instructor's code. However, when your listing and the instructor's listing are sorted, they should match line by line. Please print only the final results (i.e., all possible orderings with repetitions after all k rounds of shuffling). Do not print the intermediate results.
It is likely that your functions used in HW07
require some adjustments. ()
More specifically, you probably have to add some
more parameters to the functions written for HW07
in order to keep track of how many times the cards have been shuffled or how
many more rounds of shuffling remain.
One purpose of this assignment is to
encourage you to think about how to modify the program written for HW07 for this assignment. When you reuse the code
from HW07, be sure to remove the
pairs in the program.
Tips for getting started
repeat_shuffle(…)is similar to shuffle in HW07, except that it has an additional parameter to keep track of the number of rounds (int k) to shuffle cards.
repeat_shuffle(…)can be written as a part of a recursive paradigm, but it does not call itself. (In all exercises so far, all recursive functions call themselves directly.) Here, you may want to consider the case that
repeat_shuffle(…)calls another function, which then calls
repeat_shuffle(…), but with a smaller problem size. (What is the problem size in this recursive paradigm?) In other words,
repeat_shuffle(…)is called recursively in an indirect fashion.
When the number of rounds of shuffling is zero, what should
repeat_shuffle(…)do? This is the terminating condition for
repeat_shuffle(…). Recall that this function is supposed to print possible outcomes (with repetitions) after k rounds of shuffling. If k = 0, what should be printed? Are there other terminating conditions?
If the number of rounds (int k) of shuffling is greater than zero,
repeat_shuffle(…)should perform what you did in HW07, i.e., find all possible pairs of dividing cards, and for each pair, perform interleaving.
- When you are done with interleaving an upper deck and lower deck and obtain a complete deck of cards, you have completed one round of shuffling. Now, you have to perform (k-1) more rounds of shuffling. What function can you call to perform (k-1) rounds of shuffling of a deck of cards?
If you know the answers to these questions, your shuffle.c in
should look very similar to
shuffle.c in HW07.
You can also have an implementation that uses an array to store the results of one round of shuffling. Another round of shuffling can then be applied to each deck in the array. You would have to allocate space for the storage of intermediate results, and you should also be responsible for freeing the space when you no longer need them.
Tips for testing
First, check whether you have correct number of lines for the output for a given deck size and k (# of rounds).
You may wish to modify your
to accept two command-line arguments:
the number of cards in a deck (
the number of rounds of shuffling to be performed (
Too many rounds of shuffling will generate a large number of possible orderings. This may affect your testing in three ways:
- Your implementation may require you to allocate memory to store the orderings. If the number of rounds of shuffling is too high, you may run out of memory. (If you run out of memory, you should free the memory you have allocated so far, and return EXIT_FAILURE from the main function). Therefore, it is important that after you call malloc, you always check to see whether the malloc function is successful in returning a non-NULL address.
For your testing, you probably want to save the output to a file.
./shuffle 4 3 > ordering_outputThe screen output will be redirected and be stored in the file ordering_output. Too many rounds of shuffling may result in an extremely large file, and you may run out of disk quota.Therefore, you should not attempt a large number of rounds of shuffling during testing AND also redirect the screen output to a file. It is fine to attempt a large number of rounds of shuffling, without redirecting the screen output to a file, to stress test your memory allocation, if necessary.
- Depending on your implementation, you may have a deep recursion that exhaust all space on the call stack.
- Your submission must contain each of the following files, as specified:
file contents shuffle.c functions
repeat shuffle(CardDeck orig deck, int k)→ return type: void
- orig_deck contains the number of cards
- The number of upper-low deck pairs should be the number of cards - 1.
- If (k ≤ 0), no shuffling, print the only possible outcome.
Otherwise, for each pair of upper and lower decks, interleave the cards
interleave(…), when the newly shuffled deck is complete, you will perform another k-1 rounds of shuffling with the new deck.
- Print only the results obtained after k rounds of shuffling
divide(CardDeck orig deck, CardDeck ✶ upper decks, CardDeck ✶ lower decks)→ return type: voidDivide a deck into into pairs of upper and lower decks.
- Follow the spec in HW07.
interleave(CardDeck upper deck, CardDeck lower deck)→ return type: voidPrint all possible interleavings of upper_deck with lower_deck.
- Follow the spec in HW07.
shuffle(CardDeck orig deck)→ return type: voidGenerate all possible decks that could result from one shuffle.
- Follow the spec in HW07.
- Submissions must meet the code quality standards and the course policies on homework and academic integrity.
To submit HW08, type
264submit HW08 shuffle.c
from inside your hw08 directory.
The pre-tester for HW08 has been released and is ready to use.
Answers to common questions may be posted here later.
|10/10/2017||Modified starter code to include headers for HW07 functions in shuffle.h. Clarified that only the helper functions from HW07 change. Improved layout of pre-tester and submission instructions. Added table of contents.|
|10/11/2017||Added note about pretester. Further clarified that parameters may be changed only on helper functions.|