"""Characters at work: the Murnaghan-Nakayama rule (border strips), Kostka numbers by listing semistandard tableaux, Young's rule checked on
permutation characters, the branching rule on dimensions, and Schur-Weyl dimensions.  Standard library only."""
from itertools import permutations, product
from math import factorial, prod
from functools import lru_cache

def partitions(n, m=None):
    m = n if m is None else m
    if n == 0: yield (); return
    for k in range(min(n, m), 0, -1):
        for rest in partitions(n - k, k): yield (k,) + rest

def hooks(lam):
    conj = [sum(1 for x in lam if x > j) for j in range(lam[0])] if lam else []
    return [[lam[i] - j - 1 + conj[j] - i - 1 + 1 for j in range(lam[i])] for i in range(len(lam))]

def f_hook(lam): return factorial(sum(lam)) // prod(h for r in hooks(lam) for h in r)

def dim_gl(lam, m):
    """number of semistandard tableaux with entries 1..m, by the hook content formula"""
    num = prod(m + j - i for i, r in enumerate(lam) for j in range(r)); den = prod(h for r in hooks(lam) for h in r)
    assert num % den == 0; return num // den

def remove_strips(lam, r):
    """border strips of size r that can be removed from lam: (smaller partition, height = rows spanned - 1)"""
    out = []
    # every partition nu contained in lam with |lam/nu| = r whose skew shape is connected and has no 2x2 block
    n = sum(lam)
    for nu in partitions(n - r):
        if len(nu) > len(lam) or any(nu[i] > lam[i] for i in range(len(nu))): continue
        cells = {(i, j) for i in range(len(lam)) for j in range(lam[i]) if j >= (nu[i] if i < len(nu) else 0)}
        if any((i + 1, j) in cells and (i, j + 1) in cells and (i + 1, j + 1) in cells for (i, j) in cells): continue
        seen, stack = set(), [next(iter(cells))] if cells else []
        while stack:
            c = stack.pop()
            if c in seen: continue
            seen.add(c); stack += [d for d in [(c[0]+1, c[1]), (c[0]-1, c[1]), (c[0], c[1]+1), (c[0], c[1]-1)] if d in cells]
        if seen == cells: out.append((nu, len({i for i, _ in cells}) - 1))
    return out

@lru_cache(maxsize=None)
def mn(lam, mu):
    if not mu: return 1 if not lam else 0
    return sum((-1) ** h * mn(nu, mu[1:]) for nu, h in remove_strips(lam, mu[0]))

def kostka_bruteforce(lam, mu):
    """list semistandard tableaux of shape lam with content mu: rows weakly increase, columns strictly increase"""
    cells = [(i, j) for i in range(len(lam)) for j in range(lam[i])]; k = len(mu); count = 0
    def rec(idx, T, used):
        nonlocal count
        if idx == len(cells):
            count += (used == list(mu)); return
        i, j = cells[idx]
        for v in range(k):
            if used[v] >= mu[v]: continue
            if j > 0 and T[(i, j - 1)] > v: continue
            if i > 0 and T[(i - 1, j)] >= v: continue
            T[(i, j)] = v; used[v] += 1; rec(idx + 1, T, used); used[v] -= 1; del T[(i, j)]
    rec(0, {}, [0] * k); return count

def perm_char(mu, nu):
    """number of tabloids of shape mu fixed by a permutation of cycle type nu"""
    @lru_cache(maxsize=None)
    def f(i, rem):
        if i == len(nu): return 1 if not any(rem) else 0
        return sum(f(i + 1, rem[:r] + (c - nu[i],) + rem[r + 1:]) for r, c in enumerate(rem) if c >= nu[i])
    return f(0, tuple(mu))

def removable(lam): return [tuple(x for x in lam[:i] + (lam[i] - 1,) + lam[i + 1:] if x) for i in range(len(lam)) if i == len(lam) - 1 or lam[i] > lam[i + 1]]

if __name__ == "__main__":
    for n in range(1, 8):
        P = list(partitions(n))
        for mu in P:
            for nu in P:
                assert perm_char(mu, nu) == sum(kostka_bruteforce(lam, mu) * mn(lam, nu) for lam in P), (mu, nu)   # Young's rule + MN
        for lam in P:
            if n > 1: assert sum(f_hook(r) for r in removable(lam)) == f_hook(lam)                                 # branching, dimensions
        for m in range(1, 6): assert sum(f_hook(l) * (dim_gl(l, m) if len(l) <= m else 0) for l in P) == m ** n     # Schur-Weyl
        print(f"n = {n}: Murnaghan-Nakayama + Kostka numbers reproduce the permutation characters; branching and Schur-Weyl dimensions agree")
    print("chi^(2,2) at (2,2) =", mn((2, 2), (2, 2)), "; chi^(3,1) at (4) =", mn((3, 1), (4,)), "; chi^(3,2,1) at (3,2,1) =", mn((3, 2, 1), (3, 2, 1)))
    print("Kostka (3,1) vs (2,1,1):", kostka_bruteforce((3, 1), (2, 1, 1)), "; (2,2) vs (2,2):", kostka_bruteforce((2, 2), (2, 2)))