# Permutations

## Coercion

### `G ! g: GrpPerm, GrpPermElt -> GrpPermElt`

Given a subgroup $G$ of ${\operatorname{Sym}}(X)$ and a permutation $g$ belonging to ${\operatorname{Sym}}(X)$ that is contained in $G$, embed $g$ in $G$. Thus, this operator changes the parent of $g$ to be $G$.

### `G !! H: GrpPerm, GrpPerm -> GrpPerm`

Given a group $H$ whose natural $G$-set $X$ is a subset of the natural $G$-set $Y$ for the group $G$, embed $H$ as a subgroup of $G$. The operator fails if the image of $H$ in ${\operatorname{Sym}}(Y)$ is not a subgroup of $G$.

## Arithmetic with Permutations

### `g * h: GrpPermElt, GrpPermElt -> GrpPermElt`

Product of permutation $g$ and permutation $h$, where $g$ and $h$ belong to the same generic group $U$. If $g$ and $h$ both belong to the same proper subgroup $G$ of $U$, then the result will be returned as an element of $G$; if $g$ and $h$ belong to subgroups $H$ and $K$ of a subgroup $G$ of $U$, then the product is returned as an element of $G$. Otherwise, the product is returned as an element of $U$.

### `g ^ n: GrpPermElt, RngIntElt -> GrpPermElt`

The $n$-th power of the permutation $g$, where $n$ is a positive, negative or zero integer.

### `g / h: GrpPermElt, GrpPermElt -> GrpPermElt`

Product of the permutation $g$ by the inverse of the permutation $h$, i.e. the element $g*h^{-1}$. Here $g$ and $h$ must belong to the same generic group $U$. The rules for determining the parent group of $g / h$ are the same as for $g*h$.

### `g ^ h: GrpPermElt, GrpPermElt -> GrpPermElt`

Conjugate of the permutation $g$ by the permutation $h$, i.e. the element $h^{-1}*g*h$. Here $g$ and $h$ must belong to the same generic group $U$. The rules for determining the parent group of $g^h$ are the same as for $g*h$.

### `(g, h): GrpPermElt, GrpPermElt -> GrpPermElt`

Commutator of the permutations $g$ and $h$, i.e. the element $g^{-1}*h^{-1}*g*h$. Here $g$ and $h$ must belong to the same generic group $U$. The rules for determining the parent group of $(g, h)$ are the same as those for $g*h$.

### `(g₁, ..., gᵣ): GrpPermElt, ..., GrpPermElt -> GrpPermElt`

Given $r$ permutations $g_1, \ldots, g_r$ belonging to a common group, return their commutator. Commutators are *left-normed*, so they are evaluated from left to right.

## Properties of Permutations

### `CycleStructure(g): GrpPermElt -> [ <RngIntElt, RngIntElt> ]`

Given a permutation $g$ belonging to a group of degree $n$, return the partition of $n$ corresponding to the cycles of $g$. This partition is returned in the form of a sequence $Q$ of pairs, where the terms of $Q$ correspond to the distinct cycle lengths of $g$. The value of the term $Q[i]$ is a tuple $< l_i, n_i >$ belonging to ${\mathbb{Z}}\times {\mathbb{Z}}$. Here $l_i$ is the length of a cycle of $g$ and $n_i$ is the number of cycles of length $l_i$.

### `Degree(g): GrpPermElt -> RngIntElt`

Given a permutation $g$, return the degree of $g$, i.e. the number of points moved by $g$.

### `IsEven(g): GrpPermElt -> BoolElt`

Returns `true` if the permutation $g$ is an even permutation, `false` otherwise.

### `Sign(g): GrpPermElt -> RngIntElt`

Return 1 if the permutation $g$ is even, return -1 if $g$ is odd.

### `Order(g): GrpPermElt -> RngIntElt`

Order of the permutation $g$.

## Predicates for Permutations

### `g eq h: GrpPermElt, GrpPermElt -> BoolElt`

Given permutations $g$ and $h$ belonging to the same generic group, return `true` if $g$ and $h$ are the same element, `false` otherwise.

### `g ne h: GrpPermElt, GrpPermElt -> BoolElt`

Given permutations $g$ and $h$ belonging to the same generic group, return `true` if $g$ and $h$ are distinct elements, `false` otherwise.

### `IsId(g): GrpPermElt -> BoolElt`

### `IsIdentity(g): GrpPermElt -> BoolElt`

Returns `true` if the permutation $g$ is the identity permutation.

### `Example: Arithmetic (ex-531aba)`

We illustrate the permutation operations by applying them to some elements of ${\operatorname{Sym}}(9)$.

```magma
> G := Sym(9);
> x := G ! (1,2,4)(5,6,8)(3,9,7);
> y := G ! (4,5,6)(7,9,8);
> x*y;
(1, 2, 5, 4)(3, 8, 6, 7)
> x^-1;
(1, 4, 2)(3, 7, 9)(5, 8, 6)
> x^2;
(1, 4, 2)(3, 7, 9)(5, 8, 6)
> x / y;
(1, 2, 6, 9, 8, 4)(3, 7)
> x^y;
(1, 2, 5)(3, 8, 9)(4, 7, 6)
> (x, y);
(1, 7, 3, 6)(4, 5, 9, 8)
> x^y eq y^x;
false
> CycleStructure(x^2*y);
[ <6, 1>, <2, 1>, <1, 1> ]
> Degree(y);
6
> Order(x^2*y);
6

```

## Set Operations

The creation of a base and strong generating set (BSGS) for a permutation group $G$ provides us with a very compact representation of the set of elements of $G$. A particular BSGS imposes an order on the elements of $G$ (lexicographic ordering of base images). It thus makes sense to talk about the ‘number’ of a group element relative to a particular BSGS.

### `G * H: GrpPerm, GrpPerm -> { GrpPermElt }`

Given permutation groups $G$ and $H$, where $G$ and $H$ both belong to the same generic group, form the set product $\{ g*h | g\in G, h\in H \}$ as a set of group elements.

### `ElementSet(G, H): GrpPerm, GrpPerm -> { GrpPermElt }`

Given a group $G$ and a subgroup $H$ of $G$, return the elements of $H$ in the form of a set of elements of $G$. This function is only applicable to very small groups.

### `NumberingMap(G): GrpPerm -> Map`

A bijective mapping from the group $G$ onto the set of integers $\{ 1 \ldots |G| \rbrace$. The actual mapping depends upon the base and strong generating set chosen for $G$.

### `RandomProcess(G): GrpPerm -> Process`

```magma
Slots   : RngIntElt                    Default: 10
Scramble: RngIntElt                    Default: 20
```

Create a process to generate randomly chosen elements from the finite group $G$. The process is based on the product-replacement algorithm of [[Celler *et al.*, 1995](../../references.md#cite-randomelements)], modified by the use of an accumulator. At all times, $N$ elements are stored where $N$ is the maximum of the specified value for `Slots` and `Ngens`$(G) + 1$. Initially, these are just the generators of $G$. As well, one extra group element is stored, the accumulator. Initially, this is the identity. Random elements are now produced by successive calls to `Random(P)`, where $P$ is the process created by this function. Each such call chooses one of the elements in the slots and multiplies it into the accumulator. The element in that slot is replaced by the product of it and another randomly chosen slot. The random value returned is the new accumulator value. Setting `Scramble := m` causes $m$ such operations to be performed before the process is returned.

### `Random(G: parameters): GrpPerm -> GrpPermElt`

```magma
Short: BoolElt                    Default: false
```

A randomly chosen element for the group $G$. If a BSGS is known for $G$, then the distribution will be uniform over $G$. If no BSGS is known, then the *random* element is chosen by multiplying out a *random* word in the generators. Since it is usually not practical to choose words long enough to properly sample the elements of $G$, the element returned will usually be biased. The boolean-valued parameter `Short` is used in this situation to indicate that a short word will suffice. Thus, if `Random` is invoked with `Short` assigned the value `true` then the element is constructed using a short word.

### `Random(P): Process -> GrpPermElt`

Given a random element process $P$ created by the function `RandomProcess(G)` for the finite group $G$, construct a random element of $G$ by forming a random product over the expanded generating set constructed when the process was created. For large degree groups, or groups for which a BSGS is not known, this function should be used in preference to `Random(G)`.

### `Representative(G): GrpPerm -> GrpPermElt`

### `Rep(G): GrpPerm -> GrpPermElt`

An element chosen from the permutation group $G$.

### `Example: Set Operations (ex-80e2ef)`

We use the function `NumberingMap` to construct the multiplication table for the dihedral group of order $12$.

```magma
> G := DihedralGroup(GrpPerm, 6);
> f := NumberingMap(G);
> [ [ f(x*y) : y in G ] : x in G ];
[
    [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ],
    [ 2, 3, 4, 5, 6, 1, 12, 7, 8, 9, 10, 11 ],
    [ 3, 4, 5, 6, 1, 2, 11, 12, 7, 8, 9, 10 ],
    [ 4, 5, 6, 1, 2, 3, 10, 11, 12, 7, 8, 9 ],
    [ 5, 6, 1, 2, 3, 4, 9, 10, 11, 12, 7, 8 ],
    [ 6, 1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 7 ],
    [ 7, 8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6 ],
    [ 8, 9, 10, 11, 12, 7, 6, 1, 2, 3, 4, 5 ],
    [ 9, 10, 11, 12, 7, 8, 5, 6, 1, 2, 3, 4 ],
    [ 10, 11, 12, 7, 8, 9, 4, 5, 6, 1, 2, 3 ],
    [ 11, 12, 7, 8, 9, 10, 3, 4, 5, 6, 1, 2 ],
    [ 12, 7, 8, 9, 10, 11, 2, 3, 4, 5, 6, 1 ]
]

```

### `Example: SetOperations 2 (ex-6247bb)`

We illustrate the use of the function `Random` using the wreath product of the symmetric group of degree $4$ and the cyclic group of order $6$.

```magma
> G := WreathProduct( Sym(4), CyclicGroup(GrpPerm, 6));
> G;
Permutation group G acting on a set of cardinality 24
    (1, 5, 9, 13, 17, 21)(2, 6, 10, 14, 18, 22) (3, 7, 11, 15, 19, 23)
        (4, 8, 12, 16, 20, 24)
    (1, 2, 3, 4)
    (1, 2)
> Order(G);
1146617856
> Random(G);
(1, 17, 12, 4, 18, 10, 3, 20, 9, 2, 19, 11)(5, 22, 13, 6, 21, 15)
    (7, 24, 16)(8, 23, 14)

```

We display the cycle structures of 10 random elements of $G$.

```magma
> R := [ CycleStructure(Random(G)) : i in [1..10] ];
> R;
[
    [ <6, 1>, <3, 6> ],
    [ <9, 1>, <6, 2>, <3, 1> ],
    [ <9, 2>, <3, 2> ],
    [ <12, 1>, <9, 1>, <3, 1> ],
    [ <18, 1>, <6, 1> ],
    [ <18, 1>, <6, 1> ],
    [ <12, 1>, <6, 2> ],
    [ <6, 3>, <2, 3> ],
    [ <6, 1>, <4, 3>, <2, 3> ],
    [ <6, 3>, <3, 2> ]
]

```