Systematic listing and counting

"""Organised lists: outfits, arrangements and handshakes.

A computer is very good at following a system. The program lists outfits
branch by branch, as in a tree diagram, and checks the product rule m x n
for every m and n up to 6. It lists every order of 3 and of 4 children in a
row. Finally it counts handshakes two ways - as ordered pairs (who reaches
out first) and as unordered pairs - to show the double counting.

Runs unchanged in the browser (Pyodide) using only the standard library.
"""

import textwrap
from itertools import combinations, permutations, product

SHIRTS = ["red", "blue", "yellow"]
TROUSERS = ["black", "brown"]

def tree_list(first, second):
    """List every (first, second) pair, branch by branch."""
    return [(a, b) for a in first for b in second]

def product_rule_holds(max_size):
    """Check len(tree_list) == m * n for all 1 <= m, n <= max_size."""
    for m in range(1, max_size + 1):
        for n in range(1, max_size + 1):
            listed = tree_list(range(m), range(n))
            if len(listed) != m * n or len(set(listed)) != m * n:
                return False
    return True

def rows(children):
    """Every order of the children in a row, as strings."""
    return ["".join(p) for p in permutations(children)]

def handshakes(n):
    """Each handshake among n people once: pairs (i, j) with i < j."""
    return list(combinations(range(1, n + 1), 2))

def ordered_pairs(n):
    """Pairs (i, j) of different people where order matters."""
    return [(i, j) for i, j in product(range(1, n + 1), repeat=2) if i != j]

def main():
    outfits = tree_list(SHIRTS, TROUSERS)
    print("Tree diagram, branch by branch:")
    for shirt in SHIRTS:
        ends = ", ".join(f"{s}+{t}" for s, t in outfits if s == shirt)
        print(f"  {shirt:<7}-> {ends}")
    print(f"{len(SHIRTS)} shirts x {len(TROUSERS)} trousers"
          f" = {len(outfits)} outfits, all different: "
          f"{len(set(outfits)) == len(outfits)}")
    print(f"Product rule m x n checked for all m, n up to 6:"
          f" {product_rule_holds(6)}")
    print()
    print("Ana, Bo and Chen in a row: " + " ".join(rows("ABC")))
    four = rows("ABCD")
    print(f"Four children: {len(four)} orders, all different:"
          f" {len(set(four)) == len(four)}")
    print()
    print("People  handshakes  ordered pairs  n x (n - 1) / 2")
    for n in range(2, 9):
        print(f"{n:>6}  {len(handshakes(n)):>10}  {len(ordered_pairs(n)):>13}"
              f"  {n * (n - 1) // 2:>15}")
    print("Ordered pairs count every handshake twice: A-B and B-A.")
    print()
    print(textwrap.fill(
        "Epistemic status: exact and exhaustive for the sizes shown - every "
        "list was built and counted. It does not prove the patterns for "
        "bigger numbers; the lesson's tree-diagram argument and the Lean "
        "proofs do that.",
        width=78,
    ))

if __name__ == "__main__":
    main()

"""Guessing versus a system: how often does guessing miss an outfit?

There are 4 shirts and 3 pairs of trousers: 12 outfits. A "guesser" names
outfits at random, writes down each new one, and gives up after a few
guesses in a row that bring nothing new ("I can't think of any more").
The program simulates many guessers (with a fixed seed, so every run is the
same) and counts how often they really found all 12. A systematic list
finds all 12 in exactly 12 steps, every time.

Runs unchanged in the browser (Pyodide) using only the standard library.
"""

import random
import textwrap
from fractions import Fraction

OUTFITS = [(s, t) for s in range(4) for t in range(3)]

def guess_until_bored(rng, patience):
    """Guess random outfits; stop after `patience` guesses with nothing new.

    Returns the set of different outfits found.
    """
    found = set()
    misses = 0
    while misses < patience and len(found) < len(OUTFITS):
        outfit = rng.choice(OUTFITS)
        if outfit in found:
            misses += 1
        else:
            found.add(outfit)
            misses = 0
    return found

def guesses_to_find_all(rng):
    """Number of random guesses until every outfit has appeared."""
    found = set()
    guesses = 0
    while len(found) < len(OUTFITS):
        found.add(rng.choice(OUTFITS))
        guesses += 1
    return guesses

def expected_guesses(n):
    """Exact average number of guesses to see all n outfits: n(1 + ... + 1/n)."""
    return n * sum(Fraction(1, k) for k in range(1, n + 1))

def main():
    rng = random.Random(2024)
    runs = 2000
    print(f"{len(OUTFITS)} outfits. A system lists all of them in 12 steps.")
    print()
    print("Guessers who stop after some guesses in a row with nothing new:")
    print("  stop after   found all 12   average found")
    for patience in (3, 5, 10):
        results = [len(guess_until_bored(rng, patience)) for _ in range(runs)]
        complete = sum(r == len(OUTFITS) for r in results)
        print(f"  {patience:>2} misses   {100 * complete / runs:>9.1f} %"
              f"   {sum(results) / runs:>13.2f}")
    print()
    sims = [guesses_to_find_all(rng) for _ in range(runs)]
    exact = expected_guesses(len(OUTFITS))
    print("Guessers who never give up need, on average:")
    print(f"  simulated: {sum(sims) / runs:.2f} guesses"
          f"   exact: {float(exact):.2f} guesses")
    print(f"  (the exact value is 12 x (1 + 1/2 + ... + 1/12) = {exact})")
    print()
    print(textwrap.fill(
        f"Epistemic status: the percentages are statistical evidence from "
        f"{runs} simulated guessers per row (seeded, so repeatable); another "
        "seed gives slightly different numbers. The exact average comes from "
        "a short probability argument, not from the simulation. Guessing can "
        "never guarantee that nothing is missed; only a system can.",
        width=78,
    ))

if __name__ == "__main__":
    main()