Lab
The Elevens Game
Activity 3: Shuffling the Cards in a Deck
Introduction:
Think about how you shuffle a deck of cards by hand. How well do you think it randomizes the cards in the deck?
Exploration:
We now consider the shuffling of a deck, that is, the permutation of its cards into a random-looking sequence. A requirement of the shuffling procedure is that any particular permutation has just as much chance of occurring as any other. We will be using the Math.random method to generate random numbers to produce these permutations.
Several ideas for designing a shuffling method come to mind. We will consider two:
Perfect Shuffle
Card players often shuffle by splitting the deck in half and then interleaving the two half-decks, as shown below.
This procedure is called a perfect shuffle if the interleaving alternates between the two half-decks. Unfortunately, the perfect shuffle comes nowhere near generating all possible deck permutations. In fact, eight shuffles of a 52-card deck return the deck to its original state!
Consider the following “perfect shuffle” algorithm that starts with an array named cards that contains 52 cards and creates an array named shuffled.
Initialize shuffled to contain 52 “empty” elements. Set k to 0.
For j = 0 to 25,
−– Copy cards[j] to shuffled[k];
−– Set k to k+2. Set k to 1.
For j = 26 to 51,
−– Copy cards[j] to shuffled[k];
–− Set k to k+2.
This approach moves the first half of cards to the even index positions of shuffled, and it moves the second half of cards to the odd index positions of shuffled.
The above algorithm shuffles 52 cards. If an odd number of cards is shuffled, the array shuffled has one more even-indexed position than odd-indexed positions. Therefore, the first loop must copy one more card than the second loop does. This requires rounding up when calculating the index of the middle of the deck. In other words, in the first loop j must go up to (cards.length + 1) / 2, exclusive, and in the second loop j most begin at (cards.length + 1) / 2.
Selection Shuffle
Consider the following algorithm that starts with an array named cards that contains 52 cards and creates an array named shuffled. We will call this algorithm the “selection shuffle.”
Initialize shuffled to contain 52 “empty” elements.
Then for k = 0 to 51,
−– Repeatedly generate a random integer j between 0 and 51, inclusive until cards[j] contains a card (not marked as empty);
−– Copy cards[j] to shuffled[k];
−– Set cards[j] to empty.
This approach finds a suitable card for the kth position of the deck. Unsuitable candidates are any cards that have already been placed in the deck.
While this is a more promising approach than the perfect shuffle, its big defect is that it runs too slowly. Every time an empty element is selected, it has to loop again. To determine the last element of shuffled requires an average of 52 calls to the random number generator.
A better version, the “efficient selection shuffle,” works as follows:
For k = 51 down to 1,
−– Generate a random integer r between 0 and k, inclusive;
−– Exchange cards[k] and cards[r].
This has the same structure as selection sort:
For k = 51 down to 1,
−– Find r, the position of the largest value among cards[0] through cards[k];
−– Exchange cards[k] and cards[r].
This way, the “efficient” selection shuffle algorithm does not require a loop to find the largest (or smallest) value to swap, so it works quicker than the selection shuffle seen above.
Questions:
- Write a static method named flip that simulates a flip of a weighted coin by returning either “heads” or “tails” each time it is called. The coin is twice as likely to turn up heads as tails. Thus, flip should return “heads” about twice as often as it returns “tails.”
- Write a static method named “arePermutations” that, given two int arrays of the same length but with no duplicate elements, returns true if one array is a permutation of the other (i.e., the arrays differ only in how their contents are arranged). Otherwise, it should return false.
- Suppose that the initial contents of the values array in Shuffler.java are {1, 2, 3, 4}. For what sequence of random integers would the efficient selection shuffle change values to contain {4, 3, 2, 1}?
Teacher’s Comments:
1. If you run the two methods with VALUE_COUNT = 10, how often would there be duplicate results?
2. Can the number of duplicate results show the efficiency of the two different shuffles?
https://www.youtube.com/watch?v=hPNRtbbf-Jg
