Tag Archives: Algorithm

Card and Deck – Deal and Shuffle

There are a lot of websites showing how do you write code for the classes Card and Deck implementing two key operations – deal and shuffle. And almost all of them have an O(N) solution for shuffling the cards (N = 52, the number of cards). (For example, http://math.hws.edu/javanotes/c5/s4.html and awesome discussion at http://www.codinghorror.com/blog/2007/12/shuffling.html, or just search on Google for “card deck deal shuffle code” or even “card deck deal shuffle code optimized“)

Recently, somebody asked me – if there’s a better solution.

Now let me just generalize this problem – we have a collection of N items which need to dealed and shuffled. The order in which the items are dealed should not be predictable (that’s what randomness means, right?). Think… can we do it in O(1) with minimal memory? I did it!

For the sake of simplicity, let’s number the cards 1-52 and define the interface for the IDeck as follows:

interface IDeck
{
    void Shuffle();          //Shuffles so that the "fresh" deal can start
    int Deal();              //Gives me the next card
    int Remaining { get; }   //Returns the number of cards remaining in the deck
}

Now, let’s look at the following solution…

We need to have an array that will hold these cards, in this case – an array of int – int[] cards.
Then we need an index/count indicating how many cards have been dealt or remaining – int index.

Now, dealing is simple – start picking up the items from the start / end and update value of index appropriately. For example, we can initially have index = cards.length - 1 and decrement it each time deal is done.

But the problem is that during shuffle, we need to randomly put all the cards in the array cards. Now, to randomize and shuffle, we’ll need another temporary array so that we can start picking up the cards randomly and place them across.

Well, almost all of the solutions that Google gave me do the same.

Let’s approach is slightly differently… focus on what we need.

Read more …