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.

The sum-total of shuffle + deal is to start giving out the cards in random order… an order which is not predictable.

Let’s first try to minimize the memory… can we do the shuffling using just one array?
How about just resetting the index back to its default value indicating that all the cards are in deck and shuffled.

Ouch! But we never really did shuffling. Hmmm… that’s the real trick.

Ok… so, now what? How do we deal? Because dealing from the order will give me the same cards — very predictable.
Think once again…

Can we just pick up a random index and deal the card at that index?
Now, that’s getting interesting… but the problem is where do we keep these indices?

Ok… there are only 52 cards, just use an int which lower 52-bits as flags to check which cards at which indices have already been dealt.
Looks great, or… errr… wait! How do I check which indices have been used? I need to start looking at the bits once again. Now, that’s O(N) once again.

Not looking good.

Can we just pick up a random number between 0 to number-of-cards-remaining and deal that card? Let’s call it the deal index
Looks better… but the problem is what do we do with this deal index? If we can somehow move the card at this index to somewhere on one side, we can somehow get to an O(1) solution.

And you yell, “Ouch! What did you just say? Not sure if I understood this part. Or have I?”. If you have… Hurray! You have the solution.

Here are the stepwise details:

Structure:

1. An array to keep the cards.
2. An index to indicate the number of cards in the deck (initial value as cards.length)

Shuffle:

1. Set index <– cards.length

Deal:

1. Pick a random number between 0 (inclusive) to index (exclusive). We call it deal index.
2. Swap the cards at the “deal index” and “index – 1”.
3. Decrement index by 1
4. The card at the “deal index” is the card dealt.

No loops. All fixed time operations… total cost O(1). Only one array and one integer.

Great. And the code is for the sake of completeness (written in C#).

class Deck : IDeck
{
  private int[] cards = new int[52];
  private int index;

  public Deck() {
    for(int i = 0; i < cards.Length; i++) {
      cards[i] = i + 1;
    }
    Shuffle();
  }

  public int Remaining {
    get { return index; }
  }

  public void Shuffle() {
     index = cards.Length;
  }

  public int Deal() {
     if(Remaining > 0)
     {
       //Get the random card
       int dealIndex = new Random().Next(index);
       int card = cards[dealIndex];

       //Now swap
       int tmp = cards[dealIndex];
       cards[dealIndex] = cards[index - 1];
       cards[index - 1] = tmp;

       //Update the "end point" => cards remaining / dealt
       index--;

       //Deal
       return card;
     }
     throw new InvalidOperationException();
  }
}

Enjoy!