The problem to solve is how to write a shuffling algorithm to shuffle a deck of cards.

First we will have to create a class to represent the deck of cards (52 cards in total).

Then we have to create the deck and finally to shuffle the card. Shuffling is done by a one pass algorithm O(n). We generate a random number from 0 to 51 and we swap the positions. The random number generator must be really good. The method is similar to the Knuth or Fisher-Yates shuffle.

Another alternative would be to generate a GUID and then sort the GUID thus shuffling the deck of card. A Globally Unique Identifier or GUID is a special type of identifier used in software applications in order to provide a reference number which is unique in any context.(Wikipedia) The sorting time is O(n log n). By this we avoid using a random number generator.

Some interesting discussions are made in coding horror by Jeff Atwood about the predictability of the random number generator.

We can perform an initial cut on the deck of cards before applying GUID or the shuffling algorithm. The cut is done by swapping the first 26 cards with the last 26 cards.

The card class

public class Card {

//This card represents a single deck Card

//It will be used to construct a complete deck of cards (52 cards in total)

private string face; // face of card 13 ranks (A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K)

private string suit; // suit of card (“Hearts”, “Diamonds”, “Clubs, “Spades”)

// constructor

public Card(string cardFace, string cardSuit) {

face = cardFace;

suit = cardSuit;

}

// return string representation of Card

public override string ToString() {

return face + ” of ” + suit;

}

} // end class Card

And this is the shuffling implementation

// shuffle deck of Cards

//This is a one pass algorithm for shuffling N elements O(n)

public void Shuffle() {

currentCard = 0;

for (int first = 0; first < deck.Length; first++) {

// select a random number between 0 and 51

int second = randomNumbers.Next(NUMBER_OF_CARDS);

// swap current Card with randomly selected Card

Card temp = deck[first];

deck[first] = deck[second];

deck[second] = temp;

}

}

Several variable definitions are missing but are very easy to declare them.

No Responses to “Shuffling algorithm”