Permutation Groups

Permutation Groups

A permutation of a set $\{0, 1, \ldots, n-1\}$ is a bijection from the set to itself. The set of all permutations of $n$ elements forms the symmetric group $S_n$ under composition.

Representing Permutations

We represent a permutation $\sigma$ as a list where $\sigma[i]$ is the image of $i$:

# sigma: 0->1, 1->2, 2->0
sigma = [1, 2, 0]

Composition

The composition $\sigma \circ \tau$ applies $\tau$ first, then $\sigma$:

def compose(sigma, tau):
    n = len(sigma)
    return [sigma[tau[i]] for i in range(n)]

Identity and Inverse

The identity permutation is $\text{id} = [0, 1, 2, \ldots, n-1]$.

The inverse $\sigma^{-1}$ satisfies $\sigma \circ \sigma^{-1} = \text{id}$:

def inverse(sigma):
    n = len(sigma)
    inv = [0] * n
    for i in range(n):
        inv[sigma[i]] = i
    return inv

Order of a Permutation

The order of $\sigma$ is the smallest $k > 0$ such that $\sigma^k = \text{id}$. It equals the least common multiple of the lengths of its disjoint cycles.

Cycle Notation

A permutation can be decomposed into disjoint cycles. For example, $[1, 2, 0, 4, 3]$ decomposes as $(0\ 1\ 2)(3\ 4)$.

Your Task

Implement compose(sigma, tau), inverse(sigma), and perm_order(sigma) (the order of a permutation).