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.

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.

Data structure choice: A list preserves insertion order (important for a hand of cards) and supports O(1) index access for the swap operation. 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