"""Exact finite group calculations used in the Galois tutorial.

Only Python's standard library is required. Permutations use zero-based images.
compose(p, q) applies q first, then p. These finite enumerations illustrate the
proof; they do not replace the theorem for arbitrary degree.
"""
from itertools import permutations


def compose(p, q):
    """Return p∘q, with (p∘q)(i)=p[q[i]]."""
    return tuple(p[q[i]] for i in range(len(p)))


def inverse(p):
    out = [0] * len(p)
    for i, image in enumerate(p):
        out[image] = i
    return tuple(out)


def commutator(p, q):
    """p q p^-1 q^-1 measures the failure of p and q to commute."""
    return compose(compose(compose(p, q), inverse(p)), inverse(q))


def group_closure(generators, n):
    """Enumerate the subgroup generated by the supplied permutations."""
    generators = tuple(set(generators))
    if not 1 <= n <= 5:
        raise ValueError("The teaching implementation supports n=1,...,5")
    expected = list(range(n))
    if any(sorted(p) != expected for p in generators):
        raise ValueError("Each generator must permute 0,...,n-1")
    steps = tuple(set(generators + tuple(map(inverse, generators))))
    identity = tuple(expected)
    group, queue = {identity}, [identity]
    for p in queue:
        for generator in steps:
            candidate = compose(generator, p)
            if candidate not in group:
                group.add(candidate)
                queue.append(candidate)
    return frozenset(group)


def derived_subgroup(group):
    """Generate G' from ALL commutators, not merely list the commutators."""
    if not group:
        raise ValueError("A group cannot be empty")
    n = len(next(iter(group)))
    return group_closure({commutator(p, q) for p in group for q in group}, n)


def derived_series(group):
    """Stop at {e}, or retain the repeated terminal group when G'=G."""
    series = [frozenset(group)]
    while len(series[-1]) != 1:
        next_group = derived_subgroup(series[-1])
        series.append(next_group)
        if next_group == series[-2]:
            break
    return series


def parity(p):
    return sum(p[i] > p[j] for i in range(len(p))
               for j in range(i + 1, len(p))) % 2


def symmetric_group(n):
    return frozenset(permutations(range(n)))


def alternating_group(n):
    return frozenset(p for p in permutations(range(n)) if parity(p) == 0)


def cyclic_group(n):
    return group_closure([tuple((i + 1) % n for i in range(n))], n)


def example_orders():
    groups = {"C5": cyclic_group(5), "S3": symmetric_group(3),
              "S4": symmetric_group(4), "A5": alternating_group(5),
              "S5": symmetric_group(5)}
    return {name: [len(h) for h in derived_series(group)]
            for name, group in groups.items()}


if __name__ == "__main__":
    expected = {"C5": [5, 1], "S3": [6, 3, 1], "S4": [24, 12, 4, 1],
                "A5": [60, 60], "S5": [120, 60, 60]}
    actual = example_orders()
    assert actual == expected
    for name, orders in actual.items():
        print(name, " -> ".join(map(str, orders)))