# The `AbstractPermutation`

interface

The `AbstractPermutation`

interface consists of just three mandatory functions. Note that none of them is exported, hence it is safe to `import`

/`using`

the package without introducing any naming conflicts with other packages.

## Mandatory methods

The three mandatory methods are:

- a constructor,
`AbstractPermutations.degree`

and`Base.^`

.

The meaning of `degree`

doesn't have a well established tradition in mathematics. This is still ok, as long as we define its meaning with care for precision and use it in a consistent and predictable way.

`AbstractPermutations.AbstractPermutation`

— Type`AbstractPermutation`

Abstract type representing bijections of positive integers `ℕ = {1,2,…}`

finitely supported. That is, we treat permutations as functions `ℕ → ℕ`

such that for every permutation `σ`

there are only finitely many `k`

different from their image under `σ`

.

**Mandatory interface**

Subtypes `APerm <: AbstractPermutation`

must implement the following functions:

`APerm(images::AbstractVector{<:Integer}[; check::Bool=true])`

- a constructor of a`APerm`

from a vector of images. Optionally the keyword argument`check`

may be set to`false`

when the caller knows that`images`

constitute a honest permutation.`Base.:^(i::Integer, σ::APerm)`

the customary notation for the image of`i`

under`σ`

.`degree(σ::APerm)`

the minimal`d ≥ 0`

such that`σ`

fixes all`k ≥ d`

.

There is no formal requirement that the `APerm(images)`

constructor actually returns a `APerm`

. Any `AbstractPermutation`

object would do. This may be useful if constructing permutation from images is not technically feasible.

If `APerm`

is not constructable from type one needs to implement `one(::APerm)`

.

Even though `AbstractPermutation <: GroupsCore.GroupElement`

they don't necessarily implement the whole of `GroupElement`

interface, e.g. it is possible to implement `parent`

-less permutations.

**Optional interface**

`perm(σ::APerm)`

by default returns`σ`

- the "simplest" (implementation-wise) permutation underlying`σ`

.`inttype(::Type{<:APerm})`

by default returns`UInt32`

.`__unsafe_image(i::Integer, σ::APerm)`

defaults to`i^σ`

.

`AbstractPermutations.degree`

— Function`degree(σ::AbstractPermutation)`

Return a minimal number `n ≥ 0`

such that `k^σ == k`

for all `k > n`

.

Such number `n`

can be understood as a *degree* of a permutation, since we can regard `σ`

as an element of `Sym(n)`

(and not of `Sym(n-1)`

).

By this convention `degree`

of the identity permutation is equal to `0`

and it is the only permutation with this property. Also by this convention there is no permutation with `degree`

equal to `1`

.

`Base.:^`

— Method`^(i::Integer, σ::AbstractPermutation)`

Return the image of `i`

under `σ`

preserving the type of `i`

.

We consider `σ`

as a permutation of `ℕ`

(the positive integers), with finite support, so `k^σ = k`

for all `k > degree(σ)`

.

The behaviour of `i^σ`

for `i ≤ 0`

is undefined and can not be relied upon.

## Suplementary methods

Moreover there are three internal, suplementary functions that may be overloaded by the implementer, if needed (mostly for performance reasons).

`AbstractPermutations.inttype`

— Function`inttype(σ::Type{<:AbstractPermutation})`

Return the underlying "storage" integer.

**For internal use only.**

The intention is to provide optimal storage type when the `images`

vector constructor is used (to save allocations and memory copy). For example a hypothetic permutation `Perm8`

of elements up to length `255`

may alter the default to `UInt8`

.

The default is `UInt32`

.

`AbstractPermutations.perm`

— Function`perm(p::AbstractPermutation)`

Return the "bare-metal" permutation (unwrap). Return `σ`

by default.

**For internal use only.**

Provide access to wrapped permutation object. For "bare-metal" permutations this method needs to return the identical (i.e. ``===`

) object.

The intention of this method is to provide an un-wrapped permutations to computationally intensive algorithms, so that the external wrappers (if present) do not hinder the performance.

`AbstractPermutations.__unsafe_image`

— Function`__unsafe_image(i::Integer, σ::AbstractPermutation)`

The same as `i^σ`

, but assuming that `i ∈ Base.OneTo(degree(σ))`

.

The caller is responsible for checking the assumption. Failure to do so may (and probably will) lead to segfaults in the best case scenario and to silent data corruption in the worst!.

## Example implementation

For an example, very simple implementation of the `AbstractPermutation`

interface you may find in `ExamplePerms`

module defined in `perms_by_images.jl`

.

Here we provide an alternative implementation which keeps the internal storage at fixed length.

### Implementing mandatory methods

```
import AbstractPermutations
struct APerm{T} <: AbstractPermutations.AbstractPermutation
images::Vector{T}
degree::Int
function APerm{T}(images::AbstractVector{<:Integer}; check::Bool=true) where T
if check
isperm(images) || throw(ArgumentError("`images` vector is not a permutation"))
end
deg = something(findlast(i->images[i] ≠ i, eachindex(images)), 0)
return new{T}(images, deg)
end
end
```

Above we defined permutations by storing the vector of their images together with the computed degree `deg`

.

Now we need to implement the remaining two functions which will be simple enough:

```
AbstractPermutations.degree(p::APerm) = p.degree
function Base.:^(i::Integer, p::APerm)
deg = AbstractPermutations.degree(p)
# make sure that we return something of the same type as `i`
return 1 ≤ i ≤ deg ? oftype(i, p.images[i]) : i
end
```

With this the interface is implementation is complete. To test whether the implementation follows the specification a test suite is provided:

```
include(joinpath(pkgdir(AbstractPermutations), "test", "abstract_perm_API.jl"))
abstract_perm_interface_test(APerm{UInt16})
```

```
Test Summary: | Pass Total Time
AbstractPermutation API test: Main.APerm{UInt16} | 95 95 0.1s
```

### Suplementary Methods

Since in `APerm{T}`

we store images as a `Vector{T}`

, to avoid spurious allocations we may define

`AbstractPermutations.inttype(::Type{APerm{T}}) where T = T`

There is no need to define `AbstractPermutations.perm`

as `APerm`

is already very low level and suitable for high performance code-paths.

Finally to squeeze even more performance one could define `__unsafe_image`

with the same semantics as `n^σ`

under the assumption that `n`

belongs to `Base.OneTo(degree(σ))`

:

```
@inline function AbstractPermutations.__unsafe_image(n::Integer, σ::APerm)
return oftype(n, @inbounds σ.images[n])
end
```