Section 28.5 Shuffle A List
Imagine we want to program a card game. We will need the ability to simulate a deck of cards and select a hand of cards for the player. If we store the deck as a list: ["Ace", "2", "3", …] we can think of the start of the list as the “top” of the deck and the end of the list as the “bottom”. Dealing a player cards could be as simple as slicing the deck - make one slice that has the first 5 cards, that is the player’s hand, and a second slice with everything else that is the leftover cards.
However, we don’t always want to give the player the cards Ace-4. We need to shuffle the deck before trying to deal. We will explore two different algorithms for doing a shuffle before dealing cards.
To reduce the complexity, we will only deal with a deck with 13 cards. However, we will write the code so that it could work for any size deck. A good practice when problem solving is to whenever possible, solve a smaller version of the problem before scaling up to tackle the full version.
Subsection 28.5.1 Shuffle By Cuts
Our first algorithm will be to try shuffling by doing a series of “cuts”, where we split the deck in half and put the “bottom” (second) half “on top of” (in front of) the “top” (first) half.
The exercises below will guide you through writing the algorithm. In the first part, we will just make one cut and reassemble the deck so the “top” and “bottom” halves are reversed.
Checkpoint 28.5.1.
cutPoint is set to a random location in the list of cards deck. Use it to make a slice which contains list items 0 up to (but not including) the cutPoint. Store it in a new variable top and then print out top. Run the program a few times to make sure that you are printing out a random amount of the list each time. Tests 1-2 should now pass.
Now make a slice that starts at cutPoint and goes until the end. Store that slice as bottom. Print it out and make sure it has the part of the list that top does not. Tests 3-4 should now pass.
Set deck to be bottom plus top and print what deck becomes. That should reverse the order of the two halves. (Doing + will merge two lists into one big list.) Print deck to see that you did in fact cut the cards and swap the two halves.
At this point, your program should print out a deck where part of the back has been moved to the front. So hopefully, if we repeat that process a bunch of times, the deck will keep getting chopped up differently and become more and more jumbled.
Let’s test that.
Checkpoint 28.5.3.
Put your code in the loop below that repeats the whole process 10 times.
Checkpoint 28.5.4.
How does the method seem to work?
Poorly. New more cuts do not seem to mix up the deck more thoroughly.
Correct. This is a bad way to shuffle cards. Cutting the deck 10 times (or a million) is no more random than cutting it just once!
OK. Neighbor values like 4/5 or 7/8 tend to stay next to each other, but the deck is getting more mixed up.
Really???
Really well.
Really???
Subsection 28.5.2 Shuffle By Move To Back
The second algorithm we will try will be to pick one card at random from the deck (other than the last card) and move it to the end of the deck. On its own, that won’t do much, but maybe if we repeat it a bunch of times, it will work.
The exercises below will guide you through writing the algorithm.
Checkpoint 28.5.5.
The starter code makes selectIndex and sets it to a random value between 0 and 2 less than the length of the deck. (Since the last card is length - 1 and we do not want to select it).
Copy the card at that location of
selectIndex to a variable
removed. Then use the
.pop(XXX) function to remove that item from the
deck. Here is the section on
Adding and Removing Items if you need to review.
Print removed and deck. Make sure the card you “removed” is no longer in the deck. At this point the first 3 tests should pass.
Append the removed card to the end of the deck. Print the deck and verify that one random card was moved to the end. At this point the last test should pass.
The checks for this program can’t verify it works because it is doing something random. They will just make sure you have some of the basic elements that are needed. Make sure to test your program until you are sure it is working. The checks do depend on you using the specified variable names in your code.
Now we will repeat the process. Since we are only moving one card at a time, doing 10 repetitions probably won’t be enough. But let’s start with that and see if the method looks like it is working before we scale it up to more repetitions.
Checkpoint 28.5.6.
Put your existing code in the loop below that repeats the whole process 10 times.
Checkpoint 28.5.7.
How does this new method seem to work?
Poorly. Items seem to drift back to their initial positions after being moved.
Things should be more jumbled up than that.
OK. But there are still really long runs of consecutive cards (like 2-6 all in order).
It is possible that you saw this, but only if you got unlucky. Try running the program again.
Well.
This is pretty effective, though it would help to repeat the process more than 10 times.
If we really wanted to prove which method was the better way to shuffle we would need to create a measurement of randomness and then test how “random” the results of the different algorithms are. We might also need to do this to figure out the optimum number of repetitions for any particular algorithm. But the “eye test” is good enough to identify that our second algorithm is superior.
You have attempted
of
activities on this page.
