Permutations and Symmetric groups

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)

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 decomposition

A 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::AbstractVector{<: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}

SymmetricGroup{T<:Integer}

The full symmetric group singleton type. SymmetricGroup(n) constructs the full symmetric group $S_n$ on $n$-symbols. The type of elements of the group is inferred from the type of n.

Examples

julia> G = SymmetricGroup(5)
Full symmetric group over 5 elements

julia> elem_type(G)
Perm{Int64}

julia> H = SymmetricGroup(UInt16(5))
Full symmetric group over 5 elements

julia> elem_type(H)
Perm{UInt16}

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) == SymmetricGroup(4)
true

julia> p = perm"(1,3)(2,4)(10)"
(1,3)(2,4)

julia> parent(p) == SymmetricGroup(10)
true

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 Vector{Vector{Int64}}:
 [1, 3, 5]
 [2, 4]
 [6]

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

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

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 Vector{Int64}:
 3
 2
 1

julia> e = one(g)
()

julia> permtype(e)
6-element Vector{Int64}:
 1
 1
 1
 1
 1
 1

Generic.elements!(G::SymmetricGroup)

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 explicitly copy permutations intended to be stored or modified.

Examples

julia> elts = Generic.elements!(SymmetricGroup(5));


julia> length(elts)
120

julia> for p in Generic.elements!(SymmetricGroup(3))
         println(p)
       end
()
(1,2)
(1,3,2)
(2,3)
(1,2,3)
(1,3)

julia> A = collect(Generic.elements!(SymmetricGroup(3))); A
6-element Vector{Perm{Int64}}:
 (1,3)
 (1,3)
 (1,3)
 (1,3)
 (1,3)
 (1,3)

julia> unique(A)
1-element Vector{Perm{Int64}}:
 (1,3)

*(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 right and 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)

^(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(g::Perm)

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

==(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

==(G::SymmetricGroup, H::SymmetricGroup)

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 = SymmetricGroup(UInt(5))
Permutation group over 5 elements

julia> H = SymmetricGroup(5)
Permutation group over 5 elements

julia> G == H
false

rand([rng=Random.default_rng(),] G::SymmetricGroup)

Return a random permutation from G.

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:
 ⋅  1  ⋅
 ⋅  ⋅  1
 1  ⋅  ⋅

julia> Array(ans)
3×3 Matrix{Int64}:
 0  1  0
 0  0  1
 1  0  0

matrix_repr(Y::YoungTableau)

Construct sparse integer matrix representing the tableau.

Examples

julia> y = YoungTableau([4,3,1]);


julia> matrix_repr(y)
3×4 SparseArrays.SparseMatrixCSC{Int64, Int64} with 8 stored entries:
 1  2  3  4
 5  6  7  ⋅
 8  ⋅  ⋅  ⋅

emb(G::SymmetricGroup, 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(SymmetricGroup(5), [3,2,5]);


julia> f(p)
(2,5,3)

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)