There are a lot of websites showing how do you write code for the classes
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
For the sake of simplicity, let's number the cards 1-52 and define the interface for the
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 -
Then we need an index/count indicating how many cards have been dealt or remaining -
Now, dealing is simple - start picking up the items from the start / end and update value of
But the problem is that during
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
Ouch! But we never really did shuffling. Hmmm... that's the real trick.
Ok... so, now what? How do we deal? Because
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
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
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:
Great. And the code is for the sake of completeness (written in C#).
Enjoy!
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.
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 indexLooks 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:
- An array to keep the cards.
- An index to indicate the number of cards in the deck (initial value as cards.length)
- Set index <-- cards.length
- Pick a random number between 0 (inclusive) to index (exclusive). We call it deal index.
- Swap the cards at the "deal index" and "index - 1".
- Decrement index by 1
- The card at the "deal index" is the card
dealt.
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!