# Permutations and Permutation groups

AbstractAlgebra.jl provides rudimentary native support for permutation groups (implemented in `src/generic/PermGroups.jl`

). All functionality of permutations is accesible in the `Generic`

submodule.

Permutations are represented internally via vector of integers, wrapped in type `Perm{T}`

, where `T<:Integer`

carries the information on the type of elements of a permutation. Permutation groups are singleton parent objects of type `PermGroup{T}`

and are used mostly to store the length of a permutation, since it is not included in the permutation type.

Permutation groups are created using the `PermGroup`

(inner) constructor. However, for convenience we define

`PermutationGroup = PermGroup`

so that permutation groups can be created using `PermutationGroup`

instead of `PermGroup`

.

Both `PermGroup`

and `Perm`

and can be parametrized by any type `T<:Integer`

. By default the parameter is the `Int`

-type native to the systems architecture. However, if you are sure that your permutations are small enough to fit into smaller integer type (such as `Int32`

, `UInt16`

, or even `Int8`

), you may choose to change the parametrizing type accordingly. In practice this may result in decreased memory footprint (when storing multiple permutations) and noticable faster performance, if your workload is heavy in operations on permutations, which e.g. does not fit into cache of your cpu.

All the permutation group types belong to the `Group`

abstract type and the corresponding permutation element types belong to the `GroupElem`

abstract type.

`AbstractAlgebra.Generic.setpermstyle`

— Function.`setpermstyle(format::Symbol)`

Select the style in which permutations are displayed (in the REPL or in general as strings). This can be either

`:array`

- as vector of integers whose $n$-th position represents the value at $n$), or`:cycles`

- as, more familiar for mathematicians, decomposition into disjoint cycles, where the value at $n$ is represented by the entry immediately following $n$ in a cycle (the default).The difference is purely esthetical.

**Examples:**

```
julia> setpermstyle(:array)
:array
julia> Perm([2,3,1,5,4])
[2, 3, 1, 5, 4]
julia> setpermstyle(:cycles)
:cycles
julia> Perm([2,3,1,5,4])
(1,2,3)(4,5)
```

## Permutations constructors

There are several methods to construct permutations in AbstractAlgebra.jl.

- The easiest way is to directly call to the
`Perm`

(inner) constructor:

`AbstractAlgebra.Generic.Perm`

— Type.`Perm{T<:Integer}`

The type of permutations. Fieldnames:

`d::Vector{T}`

- vector representing the permutation`modified::Bool`

- bit to check the validity of cycle decomposition`cycles::CycleDec{T}`

- (cached) cycle decompositionA permutation $p$ consists of a vector (

`p.d`

) of $n$ integers from $1$ to $n$. If the $i$-th entry of the vector is $j$, this corresponds to $p$ sending $i \to j$. The cycle decomposition (`p.cycles`

) is computed on demand and should never be accessed directly. Use`cycles(p)`

instead.There are two inner constructors of

`Perm`

:

`Perm(n::T)`

constructs the trivial`Perm{T}`

-permutation of length $n$.`Perm(v::Vector{T<:Integer}[,check=true])`

constructs a permutation represented by`v`

. By default`Perm`

constructor checks if the vector constitutes a valid permutation. To skip the check call`Perm(v, false)`

.

**Examples:**

```
julia> Perm([1,2,3])
()
julia> g = Perm(Int32[2,3,1])
(1,2,3)
julia> typeof(g)
Perm{Int32}
```

Since the parent object can be reconstructed from the permutation itself, you can work with permutations without explicitly constructing the parent object.

- The other way is to first construct the permutation group they belong to. This is accomplished with the inner constructor
`PermGroup(n::Integer)`

which constructs the permutation group on $n$ symbols and returns the parent object representing the group.

`PermGroup{T<:Integer}`

The permutation group singleton type.

`PermGroup(n)`

constructs the permutation group $S_n$ on $n$-symbols. The type of elements of the group is inferred from the type of`n`

.

**Examples:**

```
julia> G = PermGroup(5)
Permutation group over 5 elements
julia> elem_type(G)
Perm{Int64}
julia> H = PermGroup(UInt16(5))
Permutation group over 5 elements
julia> elem_type(H)
Perm{UInt16}
```

A vector of integers can be then coerced to a permutation by calling a parent permutation group on it. The advantage is that the vector is automatically converted to the integer type fixed at the creation of the parent object.

**Examples:**

```
julia> G = PermutationGroup(BigInt(5)); p = G([2,3,1,5,4])
(1,2,3)(4,5)
julia> typeof(p)
Perm{BigInt}
julia> H = PermutationGroup(UInt16(5)); r = H([2,3,1,5,4])
(1,2,3)(4,5)
julia> typeof(r)
Perm{UInt16}
julia> H()
()
```

By default the coercion checks for non-unique values in the vector, but this can be switched off with `G([2,3,1,5,4], false)`

.

- Finally there is a
`perm"..."`

string macro to construct a permutation from a string input.

`AbstractAlgebra.Generic.@perm_str`

— Macro.`perm"..."`

String macro to parse disjoint cycles into

`Perm{Int}`

.Strings for the output of GAP could be copied directly into

`perm"..."`

. Cycles of length $1$ are not necessary, but can be included. A permutation of the minimal support is constructed, i.e. the maximal $n$ in the decomposition determines the parent group $S_n$.

**Examples:**

```
julia> p = perm"(1,3)(2,4)"
(1,3)(2,4)
julia> typeof(p)
Perm{Int64}
julia> parent(p) == PermutationGroup(4)
true
julia> p = perm"(1,3)(2,4)(10)"
(1,3)(2,4)
julia> parent(p) == PermutationGroup(10)
true
```

## Permutation interface

The following basic functionality is provided by the default permutation group implementation in AbstractAlgebra.jl, to support construction of other generic constructions over permutation groups. Any custom permutation group implementation in AbstractAlgebra.jl should provide these functions along with the usual group element arithmetic and comparison.

`Base.parent`

— Method.`parent(g::Perm)`

Return the parent of the permutation

`g`

.

```
julia> G = PermutationGroup(5); g = Perm([3,4,5,2,1])
(1,3,5)(2,4)
julia> parent(g) == G
true
```

`AbstractAlgebra.Generic.elem_type`

— Method.`elem_type(::Type{<:PermGroup})`

Return the type of elements of a permutation group.

`AbstractAlgebra.Generic.parent_type`

— Method.`parent_type(::Type{<:Perm})`

Return the type of the parent of a permutation.

A custom implementation also needs to implement `hash(::Perm, ::UInt)`

and (possibly) `deepcopy_internal(::Perm, ::ObjectIdDict)`

.

Permutation group elements are mutable and so returning shallow copies is not sufficient.

`getindex(a::Perm, n::Integer)`

Allow access to entry $n$ of the given permutation via the syntax `a[n]`

. Note that entries are $1$-indexed.

`setindex!(a::Perm, d::Integer, n::Integer)`

Set the $n$-th entry of the given permutation to $d$. This allows Julia to provide the syntax `a[n] = d`

for setting entries of a permutation. Entries are $1$-indexed.

Using `setindex!`

invalidates the cycle decomposition cached in a permutation, which will be computed the next time it is needed.

Given the parent object `G`

for a permutation group, the following coercion functions are provided to coerce various arguments into the permutation group. Developers provide these by overloading the permutation group parent objects.

`G()`

Return the identity permutation.

`G(A::Vector{<:Integer})`

Return the permutation whose entries are given by the elements of the supplied vector.

`G(p::Perm)`

Take a permutation that is already in the permutation group and simply return it. A copy of the original is not made if not necessary.

## Basic manipulation

Numerous functions are provided to manipulate permutation group elements.

`AbstractAlgebra.Generic.cycles`

— Method.`cycles(g::Perm)`

Decompose permutation

`g`

into disjoint cycles.Return a

`CycleDec`

object which iterates over disjoint cycles of`g`

. The ordering of cycles is not guaranteed, and the order within each cycle is computed up to a cyclic permutation. The cycle decomposition is cached in`g`

and used in future computation of`permtype`

,`parity`

,`sign`

,`order`

and`^`

(powering).

**Examples:**

```
julia> g = Perm([3,4,5,2,1,6])
(1,3,5)(2,4)
julia> collect(cycles(g))
3-element Array{Array{Int64,1},1}:
[1, 3, 5]
[2, 4]
[6]
```

Cycle structure is cached in a permutation, since once available, it provides a convenient shortcut in many other algorithms.

`AbstractAlgebra.Generic.parity`

— Method.`parity(g::Perm)`

Return the parity of the given permutation, i.e. the parity of the number of transpositions in any decomposition of

`g`

into transpositions.

`parity`

returns $1$ if the number is odd and $0$ otherwise.`parity`

uses cycle decomposition of`g`

if already available, but will not compute it on demand. Since cycle structure is cached in`g`

you may call`cycles(g)`

before calling`parity`

.

**Examples:**

```
julia> g = Perm([3,4,1,2,5])
(1,3)(2,4)
julia> parity(g)
0
julia> g = Perm([3,4,5,2,1,6])
(1,3,5)(2,4)
julia> parity(g)
1
```

`Base.sign`

— Method.`sign(g::Perm)`

Return the sign of a permutation.

`sign`

returns $1$ if`g`

is even and $-1$ if`g`

is odd.`sign`

represents the homomorphism from the permutation group to the unit group of $\mathbb{Z}$ whose kernel is the alternating group.

**Examples:**

```
julia> g = Perm([3,4,1,2,5])
(1,3)(2,4)
julia> sign(g)
1
julia> g = Perm([3,4,5,2,1,6])
(1,3,5)(2,4)
julia> sign(g)
-1
```

`AbstractAlgebra.Generic.permtype`

— Method.`permtype(g::Perm)`

Return the type of permutation

`g`

, i.e. lengths of disjoint cycles in cycle decomposition of`g`

.The lengths are sorted in decreasing order by default.

`permtype(g)`

fully determines the conjugacy class of`g`

.

**Examples:**

```
julia> g = Perm([3,4,5,2,1,6])
(1,3,5)(2,4)
julia> permtype(g)
3-element Array{Int64,1}:
3
2
1
julia> G = PermGroup(5); e = parent(g)()
()
julia> permtype(e)
6-element Array{Int64,1}:
1
1
1
1
1
1
```

`AbstractAlgebra.Generic.order`

— Method.`order(a::Perm) -> BigInt`

Return the order of permutation

`a`

as`BigInt`

.If you are sure that computation over

`T`

(or its`Int`

promotion) will not overflow you may use the method`order(T::Type, a::Perm)`

which bypasses computation with`BigInt`

s and returns`promote(T, Int)`

.

`AbstractAlgebra.Generic.order`

— Method.`order(G::PermGroup) -> BigInt`

Return the order of the full permutation group as

`BigInt`

.

Note that even an `Int64`

can be easily overflowed when computing with permutation groups. Thus, by default, `order`

returns (always correct) `BigInt`

s. If you are sure that the computation will not overflow, you may use `order(::Type{T}, ...)`

to perform computations with machine integers. Julia's standard promotion rules apply for the returned value.

Since `PermGroup`

implements the iterator protocol, you may iterate over all permutations via a simple loop:

```
for p in PermutationGroup(n)
...
end
```

Iteration over all permutations in reasonable time, (i.e. in terms of minutes) is possible when $n ≤ 13$.

You may also use the non-allocating `Generic.elements!`

function for $n ≤ 14$ (or even $15$ if you are patient enough), which is an order of magnitude faster.

`AbstractAlgebra.Generic.elements!`

— Method.`Generic.elements!(G::PermGroup)`

Return an unsafe iterator over all permutations in

`G`

. Only one permutation is allocated and then modified in-place using the non-recursive Heaps algorithm.Note: you need to explicitely copy permutations intended to be stored or modified.

**Examples:**

```
julia> elts = Generic.elements!(PermGroup(5));
julia> length(elts)
120
julia> for p in Generic.elements!(PermGroup(3))
println(p)
end
()
(1,2)
(1,3,2)
(2,3)
(1,2,3)
(1,3)
julia> A = collect(Generic.elements!(PermGroup(3))); A
6-element Array{Perm{Int64},1}:
(1,3)
(1,3)
(1,3)
(1,3)
(1,3)
(1,3)
julia> unique(A)
1-element Array{Perm{Int64},1}:
(1,3)
```

However, since all permutations yielded by `elements!`

are aliased (modified "in-place"), `collect(Generic.elements!(PermGroup(n)))`

returns a vector of identical permutations.

If you intend to use or store elements yielded by `elements!`

you need to **deepcopy** them explicitly.

## Arithmetic operators

`Base.:*`

— Method.`*(g::Perm, h::Perm)`

Return the composition $h ∘ g$ of two permutations.

This corresponds to the action of permutation group on the set

`[1..n]`

on the rightand follows the convention of GAP.If

`g`

and`h`

are parametrized by different types, the result is promoted accordingly.

**Examples:**

```
julia> Perm([2,3,1,4])*Perm([1,3,4,2]) # (1,2,3)*(2,3,4)
(1,3)(2,4)
```

`Base.:^`

— Method.`^(g::Perm, n::Integer)`

Return the $n$-th power of a permutation

`g`

.By default

`g^n`

is computed by cycle decomposition of`g`

if`n > 3`

.`Generic.power_by_squaring`

provides a different method for powering which may or may not be faster, depending on the particular case. Due to caching of the cycle structure, repeated powering of`g`

will be faster with the default method.

**Examples:**

```
julia> g = Perm([2,3,4,5,1])
(1,2,3,4,5)
julia> g^3
(1,4,2,5,3)
julia> g^5
()
```

`Base.inv`

— Method.`inv(g::Perm)`

Return the inverse of the given permutation, i.e. the permuation $g^{-1}$ such that $g ∘ g^{-1} = g^{-1} ∘ g$ is the identity permutation.

Permutations parametrized by different types can be multiplied, and follow the standard julia integer promotion rules:

```
g = rand(PermGroup(Int8(5)));
h = rand(PermGroup(UInt32(5)));
typeof(g*h)
# output
Perm{UInt32}
```

## Coercion

The following coercions are available for `G::PermGroup`

parent objects. Each of the methods perform basic sanity checks on the input which can be switched off by the second argument.

**Examples**

```
julia> PermutationGroup(4)()
()
```

Return the identity element of

`G`

.

`(G::PermGroup)(::Vector{<:Integer}[, check=true])`

Turn a vector of integers into a permutation (performing conversion, if necessary).

`(G::PermGroup)(::Perm[, check=true])`

Coerce a permutation

`p`

into group`G`

(performing the conversion, if necessary). If`p`

is already an element of`G`

no copy is performed.

`(G::PermGroup)(::String[, check=true])`

Parse the string input e.g. copied from the output of GAP. The method uses the same logic as the

`perm"..."`

macro. The string is sanitized and checked for disjoint cycles. Both`string(p::Perm)`

(if`setpermstyle(:cycles)`

) and`string(cycles(p::Perm))`

are valid input for this method.

`(G::PermGroup{T})(::CycleDec{T}[, check=true]) where T`

Turn a cycle decomposition object into a permutation.

## Comparison

`Base.:==`

— Method.`==(g::Perm, h::Perm)`

Return

`true`

if permutations are equal, otherwise return`false`

.Permutations parametrized by different integer types are considered equal if they define the same permutation in the abstract permutation group.

**Examples:**

```
julia> g = Perm(Int8[2,3,1])
(1,2,3)
julia> h = perm"(3,1,2)"
(1,2,3)
julia> g == h
true
```

`Base.:==`

— Method.`==(G::PermGroup, H::PermGroup)`

Return

`true`

if permutation groups are equal, otherwise return`false`

.Permutation groups on the same number of letters, but parametrized by different integer types are considered different.

**Examples:**

```
julia> G = PermGroup(UInt(5))
Permutation group over 5 elements
julia> H = PermGroup(5)
Permutation group over 5 elements
julia> G == H
false
```

## Misc

`Base.rand`

— Method.`rand([rng=GLOBAL_RNG,] G::PermGroup)`

Return a random permutation from

`G`

.

`AbstractAlgebra.Generic.matrix_repr`

— Method.`matrix_repr(a::Perm)`

Return the permutation matrix as a sparse matrix representing

`a`

via natural embedding of the permutation group into the general linear group over $\mathbb{Z}$.

**Examples:**

```
julia> p = Perm([2,3,1])
(1,2,3)
julia> matrix_repr(p)
3×3 SparseArrays.SparseMatrixCSC{Int64,Int64} with 3 stored entries:
[3, 1] = 1
[1, 2] = 1
[2, 3] = 1
julia> Array(ans)
3×3 Array{Int64,2}:
0 1 0
0 0 1
1 0 0
```

`AbstractAlgebra.Generic.emb`

— Method.`emb(G::PermGroup, V::Vector{Int}, check::Bool=true)`

Return the natural embedding of a permutation group into

`G`

as the subgroup permuting points indexed by`V`

.

**Examples:**

```
julia> p = Perm([2,3,1])
(1,2,3)
julia> f = Generic.emb(PermGroup(5), [3,2,5]);
julia> f(p)
(2,5,3)
```

`AbstractAlgebra.Generic.emb!`

— Method.`emb!(result::Perm, p::Perm, V)`

Embed permutation

`p`

into permutation`result`

on the indices given by`V`

.This corresponds to the natural embedding of $S_k$ into $S_n$ as the subgroup permuting points indexed by

`V`

.

**Examples:**

```
julia> p = Perm([2,1,4,3])
(1,2)(3,4)
julia> Generic.emb!(Perm(collect(1:5)), p, [3,1,4,5])
(1,3)(4,5)
```