David Owen’s blog

The deck itself is represented as an array of cards. It doesn't matter whether the cards are represented by integers, objects, or anything else, as long as the entry in the array itself is short. A pointer to a struct (in C-like languages) or a reference to an object (in most languages) would work very well.

The fair shuffling algorithm divides the deck into shuffled and unshuffled parts. In the middle of the shuffle, it might look like this, with "S" being a shuffled card and "U" unshuffled:

At each step, one of the unshuffled cards is selected uniformly randomly, and swapped with the card in the leading unshuffled spot (which may by chance be the same spot). That leading spot is then considered to be shuffled.

The algorithm starts by considering all positions to be unshuffled, and proceeds to the last position.

This algorithm produces a perfectly fair shuffle, with each card having equal probability of appearing in any spot, and each permutation having an equal chance of occurring.

After shuffling, the hand is "drawn" from the front of the deck by taking the first 7 cards. An array of these cards is then passed to whatever functions need to know the hand.

The trick is to recognize three things:

• Only the first 7 cards of the deck need to be shuffled, not all 52;
• If the functions are coded to support it, the array of the deck can be passed as the array of the hand; and,
• Because the shuffle is perfectly fair, the partially-shuffled deck can be reused in the next iteration as-is.

This means that the shuffle-and-draw loop would look something like this:

def simulate(rounds):
    global CARDS                # Array of 52 cards

    for j in range(rounds):

        for i in range(7):
            x = rand(52 - i) + i
            CARDS[i], CARDS[x] = CARDS[x], CARDS[i]

        analyze(CARDS)

This has the following runtime properties:

• Shuffle-and-draw requires only 7 randoms and 7 memory swaps.
• Indirection is minimized, which is needed if analyze must access array elements multiple times each call.
• No memory is copied or allocated.

As a result, it's a blazing-fast way to generate random hands.