Problem 29

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

Use Mersenne twister to shuffle a deck of cards

Due: February 8
Points: 6

Write a Java, C++ or Python program that outputs a list of the 52 standard playing cards in a randomly-chosen order. The card names should be printed one per line, each in a 2-character encoding like:

3S
4C
8H
AD
JD
QH
TC

(The card values are A for ace, 2-9, T for 10, and J, Q, K for Jack, Queen, King. The suits are Spades, Clubs, Hearts, and Diamonds.)

Use the Mersenne Twister algorithm to determine the random order, and use the /dev/urandom device in Linux to get the seed for the Mersenne Twister PRNG. Here is a good algorithm to choose a random ordering of an array A:

def shuffle(A):
    for i in range(0, len(A)-1):
        r = random_in_range(i+1, len(A))
        swap(A[i], A[r])

In other words, you go from the top of the deck to the bottom, each time swapping the current card with a randomly-chosen card from the rest of the deck.

I do not expect you to necessarily code the Mersenne Twister algorithm yourself (although you are free to do so!), which means you will need to find an existing implementation of this program in your chosen language. This is fine, but you need to make sure that:

  • The implementation you find doesn't require any libraries or anything. It should run without any special installations in the CS Linux environment
  • Don't break any laws. This means that the MT code you find must have an open-source license that allows you to use the code for this (educational purpose).
  • Don't violate your honor. You need to document clearly where you got the MT implementation from, in a README.txt file that you submit along with your program.

Submit your program according to the instructions on the submit page.