Card shuffling problem

A card shuffling algorithm is a method for randomly permuting a deck of cards so that every ordering is equally likely (in a “good” shuffle).

The most important and widely used algorithm is:

Fisher–Yates Shuffle (a.k.a. Knuth Shuffle)

This is the gold standard for unbiased shuffling.

Idea

You go through the deck from the last card to the first, and for each position, swap it with a randomly chosen earlier (or same) position.

Algorithm (array-based deck)

Let A be an array of n cards (array index: [0, ..., n-1]):

for i from n - 1 down to 1:
    j = random integer such that 0 ≤ j ≤ i
    swap A[i] and A[j]

Why it works

• Each card has an equal probability of ending in any position.
• It avoids subtle bias found in naive shuffles (like sorting with random comparator).

Complexity

• Time: O(n)
• Space: O(1) (in-place)

Variants you might see

1. Inside-out Fisher–Yates

Useful when building a shuffled array from scratch:

for i from 0 to n-1:
    j = random integer in [0, i]
    A[i] = A[j]
    A[j] = current element

2. Riffle shuffle (card-deck realistic)

Models human shuffling:

• Split deck into two halves
• Interleave them probabilistically

Used in probability studies, but needs many repeats (~7 riffle shuffles) to approximate randomness.

---

Practical note

In most programming languages:

• Use a built-in shuffle (e.g., random.shuffle in Python), which implements Fisher–Yates.