Permutations and Permutation groups

setpermstyle(format::Symbol)

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

• :array - as vectors 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> Generic.setpermstyle(:array)
:array

julia> perm([2,3,1,5,4])
[2, 3, 1, 5, 4]

julia> Generic.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

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)
AbstractAlgebra.Generic.perm{Int32}

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)
AbstractAlgebra.Generic.perm{Int64}

julia> H = PermGroup(UInt16(5))
Permutation group over 5 elements

julia> elem_type(H)
AbstractAlgebra.Generic.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 could 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)
AbstractAlgebra.Generic.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

parent(g::perm{T}) where T = PermGroup

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

elem_type(::Type{PermGroup{T}}) where T = perm{T}

Return the type of elements of a permutation group.

parent_type(::Type{perm{T}}) where T = PermGroup{T}

Return the type of the parent of a permutation.

cycles(g::perm{T}) where T<:Integer

Decompose permutation g into disjoint cycles.

Returns 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]

parity(g::perm{T}) where T

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{T}) where T

Return the sign of 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 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

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 BigInts and returns promote(T, Int).

order(G::PermGroup) -> BigInt

Return the order of the full permutation group as BigInt.

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{AbstractAlgebra.Generic.perm{Int64},1}:
 (1,3)
 (1,3)
 (1,3)
 (1,3)
 (1,3)
 (1,3)

julia> unique(A)
1-element Array{AbstractAlgebra.Generic.perm{Int64},1}:
 (1,3)

*(g::perm{T}, h::perm{T}) where T

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{T}, n::Integer) where T

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 particuar 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
()

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.

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

rand(G::PermGroup{T}) where {T}

Return a random permutation from G.

matrix_repr(a::perm{T}) where T

Return the permutation matrix as sparse matrix representing a via natural embedding of the permutation group into general linear group over $\mathbb{Z}$.

Examples:

julia> p = perm([2,3,1])
(1,2,3)

julia> matrix_repr(p)
3×3 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

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)

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)