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.^.
Note

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.
Note

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.

Note

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

Warn

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

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)).

Note

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(σ).

Warn

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.

Warn

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.

Warn

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(σ)).

Warn

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