Unbiased Random Permutation

An OOP card game model with a provably unbiased shuffle using Fisher-Yates.

Problem

Design classes for Card, CardDeck, and Player with standard operations (build, draw, shuffle, show hand). The shuffle must produce a uniform distribution over all permutations, no bias toward any particular ordering.

Approach

The naive approach (swap each element with a random position from 0 to n-1) produces n^n outcomes mapped onto n! permutations, which cannot divide evenly. The result is a biased shuffle.

The Fisher-Yates (Knuth) shuffle fixes this:

1. Walk backwards from index n-1 to 1.
2. At each index i, pick a random index j in [0, i].
3. Swap cards[i] and cards[j].

This generates exactly n! equally likely outcomes. To verify, the implementation includes an experiment that runs 600,000 shuffles on a small deck and checks that outcome frequencies are uniformly distributed.

A list preserves insertion order (important for a hand of cards) and supports O(1) index access for the swap. A set would lose ordering.

Implementation

import random
from collections import namedtuple
from statistics import pstdev, mean

SUITS = ['Hearts', 'Diamonds', 'Clubs', 'Spades']
VALUES = ['2', '3', '4', '5', '6', '7', '8', '9', '10', 'Jack', 'Queen', 'King']

Card = namedtuple('Card', ['suite', 'value'])


class DeckNotBuilt(Exception):
    pass


class CardDeck:
    def __init__(self, deck_size=52):
        self.cards = []
        self.deck_size = deck_size

    def build(self):
        self.cards = [Card(suite, value) for suite in SUITS
                      for value in VALUES[:self.deck_size // 4]]
        return self.cards

    def shuffle(self):
        """Fisher-Yates: O(n) in-place, uniform distribution."""
        n = len(self.cards)
        for i in range(n - 1, 0, -1):
            j = random.randint(0, i)
            self.cards[i], self.cards[j] = self.cards[j], self.cards[i]

    def draw(self):
        if not self.cards:
            raise DeckNotBuilt("No cards in the deck")
        return self.cards.pop()


class Player:
    def __init__(self, name):
        self.name = name
        self.hand = []

    def add_card_to_hand(self, card):
        self.hand.append(card)

    def show_hand(self):
        for card in self.hand:
            print(card)


def run_experiment(deck, num_shuffles):
    """Shuffle many times and record outcome frequencies."""
    outcomes = {}
    for _ in range(num_shuffles):
        deck.shuffle()
        deck_state = tuple(deck.cards)
        outcomes[deck_state] = outcomes.get(deck_state, 0) + 1
    return outcomes


def display_histogram(outcomes):
    values = outcomes.values()
    m = mean(values)
    std = pstdev(values)
    print(f"\nMean = {m:.2f}, Standard Deviation = {std:.2f}, Variance = {std**2:.2f}")
    print("\n****************** Histogram *******************")
    for outcome, frequency in sorted(outcomes.items(), key=lambda x: x[1]):
        print(f"{outcome}: {'*' * (frequency // 500)}")


def main():
    deck = CardDeck()
    deck.build()
    outcomes = run_experiment(deck, 600000)
    print(f"Total unique shuffles recorded: {len(outcomes)}")
    display_histogram(outcomes)


if __name__ == '__main__':
    main()

Complexity

• Time: O(n) per shuffle, single pass with constant-time swaps
• Space: O(1) extra, shuffle is in-place

Takeaway

Fisher-Yates is the gold standard for unbiased permutation and shows up anywhere you need fair random sampling, shuffling training data between epochs, bootstrap sampling, or generating random test splits. If your shuffle is biased, your model's evaluation is biased too.

---

Back to Software Design