Card games have been mankind's favorite passtime long before the era of computers. Many, perhaps most, popular card games have been programmed into computer software.
Every card game I have ever seen starts by shuffling the cards. The purpose of the shuffling is to rearrange the cards in a more-or-less random order.
Surprisingly, despite the popularity of card games among computer users, just about any programming textbook teaches several algorithms on how to sort a pack of cards but most offer no clue on how to shuffle it.
In this node I will present my own card-shuffling algorithm. I also hope others will present other card-shuffling algorithms.
Preliminaries
First of all, to use my algorithm we need to represent the cards as an integer array of size n, where n is the total number of cards.
For example, a typical solitaire game uses one deck of cards consisting of four suits each containing 13 cards (from ace to king). In this case, n is equal to 4 times 13, or 52.
A different game can use two decks, plus four jokers, for an n of 108, etc.
Whatever the size of n, we will have n cards which we will refer to as card[0] ... card[n-1]. Each card has a unique value in the [0...n-1] range.
It is quite simple to convert the integer value of a card into its suit and face value. For example, with n = 52 we have four suits (0...3), so any card[i] is inside the suit card[i] / 13, while its face value is card[i] MOD 13, where MOD designates modulo division.
The Algorithm
Step 1: Initialize the cards. For each i in the [0...n-1] range, set card[i] = i.
Step 2 (optional): Seed the random number generator.
Step 3: Let i = 0.
Step 4: Let j = random_number MOD n.
Step 5: Exchange the values of card[i] and card[j].
Step 6: Let i = i + 1. If i is less than n, go to step 4.
Sample Source Code
Here is a sample C function implementing the algorithm:
void shuffle(int *card, int n) {
int i, j, k;
for (i = 0; i < n; i++)
card[i] = i;
for (i = 0; i < n; i++) {
j = rand() % n;
k = card[i];
card[i] = card[j];
card[j] = k;
}
}