16.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 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.

16.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.

  1. Make a variable called cutPoint and set it to a random value between 1 and the one less than the length of the deck.

  2. Print out cutPoint. Run your program a number of times and make sure it gives you values in the range 1-11. You can remove the print once you see this is working.

  3. Once you are confident that you are picking a valid cut point, use it to make two slices: top which contains list items 0 up to (but not including) the cutPoint and bottom that contains from cutPoint on.

  4. Print out both halves. Again, run your program multiple times to make sure it works. You can remove the prints once you see this is working.

  5. 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.)

Check here for a review of Random Numbers.

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.

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.

  1. Put your existing code in a loop that repeats the whole process 10 times.

16.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.

  1. Make a variable called selectIndex and set 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).

  2. Print selectIndex and make sure it gives valid numbers each time you run the program.

  3. Copy the card at that location of selectIndex to a variable removed. Then use the .pop() function to remove that item from the deck. Here is a link to the page on using pop on a list if you need to review.

  4. Print removed and deck. Make sure the card you “removed” is no longer in the deck.

  5. Append the removed card to the end of the deck. Print the deck and verify that like one random card was moved to the end. Here is a link to the page on using append on a list.

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.

  1. Put your existing code in a loop that repeats the whole process 10 times.

Of course 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. After a certain point, once the deck is well shuffled, running any shuffle algorithm can’t make things any more random - it can just make a different random ordering. (The optimal number of repetitions for the first method we tried is just 1. Multiple cuts will never make the deck more random than just doing one cut!) But the “eye test” is good enough to identify that our second algorithm is obviously superior.

You have attempted of activities on this page