permutation_analysis.py

"""
Analyze permutations by counting elements in correct positions (fixed points).
"""

import argparse
from itertools import permutations
from collections import defaultdict
from math import factorial


def count_fixed_points(perm: tuple[int, ...]) -> int:
    """
    Count how many elements are in their correct position (1-indexed).

    Args:
        perm: A permutation tuple (e.g., (1, 3, 2, 4))

    Returns:
        Number of elements in correct position
    """
    return sum(1 for i, val in enumerate(perm, start=1) if i == val)


def analyze_permutations(n: int) -> dict[int, int]:
    """
    Enumerate all permutations of integers 1 to n and count how many
    permutations have exactly k elements in correct positions.

    Args:
        n: The size of permutations to analyze

    Returns:
        Dictionary mapping number_of_fixed_points -> count
    """
    counts = defaultdict(int)

    for perm in permutations(range(1, n + 1)):
        fixed = count_fixed_points(perm)
        counts[fixed] += 1

    return dict(counts)


def generate_table(m: int, include_percent: bool = False) -> None:
    """
    Generate a table showing permutation fixed point statistics for n = 1 to m.

    Each row represents a value of n, and columns show how many permutations
    have exactly k elements in correct positions.

    Args:
        m: Maximum n value to analyze
        include_percent: If True, show percentages alongside counts
    """
    # Collect all results
    results = {}
    max_cols = 0

    for n in range(1, m + 1):
        results[n] = analyze_permutations(n)
        max_cols = max(max_cols, max(results[n].keys()) + 1)

    # Determine column width based on whether we're showing percentages
    col_width = 13 if include_percent else 6

    # Print header
    header = "n |" + "".join(f" {k:>{col_width}}" for k in range(max_cols))
    print(header)
    print("-" * len(header))

    # Print rows
    for n in range(1, m + 1):
        row = f"{n} |"
        total = factorial(n)

        for k in range(max_cols):
            if k > n:
                # Invalid: can't have more fixed points than elements
                row += f" {'-':>{col_width}}"
            else:
                count = results[n].get(k, 0)
                if include_percent:
                    pct = (count / total) * 100
                    row += f" {count:>6}({pct:>5.2f}%)"
                else:
                    row += f" {count:>{col_width}}"
        print(row)


if __name__ == "__main__":
    parser = argparse.ArgumentParser(
        description="Analyze permutations by counting elements in correct positions"
    )
    parser.add_argument(
        "--include-percent",
        action="store_true",
        help="Include percentages in the output table",
    )
    parser.add_argument(
        "-m",
        "--max",
        type=int,
        default=8,
        help="Maximum value of n to analyze (default: 8)",
    )
    parser.add_argument(
        "--example",
        type=int,
        help="Show detailed example for specific n value",
    )

    args = parser.parse_args()

    print("Permutation Fixed Point Analysis")
    print("=" * 60)
    print()

    # Show example if requested
    if args.example:
        n = args.example
        print(f"Analysis for n={n}:")
        result = analyze_permutations(n)
        total = factorial(n)
        for fixed_points, count in sorted(result.items()):
            pct = (count / total) * 100
            print(
                f"  {fixed_points} elements in correct position: {count} permutations ({pct:.2f}%)"
            )
        print()

    # Generate table
    print(f"Table for n = 1 to {args.max}:")
    if args.include_percent:
        print("(Each cell shows count(percentage) of permutations with k fixed points)")
    else:
        print("(Each cell shows count of permutations with k fixed points)")
    print()
    generate_table(args.max, args.include_percent)