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 `deal`

ed and `shuffle`

d. The order in which the items are `deal`

ed 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 …