# Permutation S¶

Permutation(S) implements the group of all bijections on a set S, which move only a finite number of points. A permutation is considered as a map from S into S. In particular multiplication is defined as composition of maps: pi1 * pi2 = pi1 o pi2. The internal representation of permuatations are two lists of equal length representing preimages and images.

1: %

from MagmaWithUnit

*: (%, %) -> %

from Magma

/: (%, %) -> %

from Group

<=: (%, %) -> Boolean if S has OrderedSet or S has Finite

from PartialOrder

<: (%, %) -> Boolean

from PermutationCategory S

=: (%, %) -> Boolean

from BasicType

>=: (%, %) -> Boolean if S has OrderedSet or S has Finite

from PartialOrder

>: (%, %) -> Boolean if S has OrderedSet or S has Finite

from PartialOrder

^: (%, Integer) -> %

from Group

^: (%, NonNegativeInteger) -> %

from MagmaWithUnit

^: (%, PositiveInteger) -> %

from Magma

~=: (%, %) -> Boolean

from BasicType

coerce: % -> OutputForm
coerce: List List S -> %

coerce(lls) coerces a list of cycles lls to a permutation, each cycle being a list with no repetitions, is coerced to the permutation, which maps ls.i to ls.i+1, indices modulo the length of the list, then these permutations are mutiplied. Error: if repetitions occur in one cycle.

coerce: List S -> %

coerce(ls) coerces a cycle ls, i.e. a list with not repetitions to a permutation, which maps ls.i to ls.i+1, indices modulo the length of the list. Error: if repetitions occur.

coerceImages: List S -> % if S has Finite or S has IntegerNumberSystem

coerceImages(ls) coerces the list ls to a permutation whose image is given by ls and the preimage is fixed to be [1, …, n]. Note: {coerceImages(ls)=coercePreimagesImages([1, …, n], ls)}. We assume that both preimage and image do not contain repetitions.

coerceListOfPairs: List List S -> %

coerceListOfPairs(lls) coerces a list of pairs lls to a permutation. Error: if not consistent, i.e. the set of the first elements coincides with the set of second elements. coerce(p) generates output of the permutation p with domain OutputForm.

coercePreimagesImages: List List S -> %

coercePreimagesImages(lls) coerces the representation lls of a permutation as a list of preimages and images to a permutation. We assume that both preimage and image do not contain repetitions.

commutator: (%, %) -> %

from Group

conjugate: (%, %) -> %

from Group

cycle: List S -> %

from PermutationCategory S

cyclePartition: % -> Partition

cyclePartition(p) returns the cycle structure of a permutation p including cycles of length 1 only if S is finite.

cycles: List List S -> %

from PermutationCategory S

degree: % -> NonNegativeInteger

degree(p) returns the number of points moved by the permutation p.

elt: (%, S) -> S

from PermutationCategory S

eval: (%, S) -> S

from PermutationCategory S

even?: % -> Boolean

even?(p) returns true if and only if p is an even permutation, i.e. sign(p) is 1.

fixedPoints: % -> Set S if S has Finite

fixedPoints(p) returns the points fixed by the permutation p.

hash: % -> SingleInteger

from SetCategory

hashUpdate!: (HashState, %) -> HashState

from SetCategory

inv: % -> %

from Group

latex: % -> String

from SetCategory

leftPower: (%, NonNegativeInteger) -> %

from MagmaWithUnit

leftPower: (%, PositiveInteger) -> %

from Magma

leftRecip: % -> Union(%, failed)

from MagmaWithUnit

listRepresentation: % -> Record(preimage: List S, image: List S)

listRepresentation(p) produces a representation rep of the permutation p as a list of preimages and images, i.e p maps (rep.preimage).k to (rep.image).k for all indices k. Elements of S not in (rep.preimage).k are fixed points, and these are the only fixed points of the permutation.

max: (%, %) -> % if S has OrderedSet or S has Finite

from OrderedSet

min: (%, %) -> % if S has OrderedSet or S has Finite

from OrderedSet

movedPoints: % -> Set S

movedPoints(p) returns the set of points moved by the permutation p.

numberOfCycles: % -> NonNegativeInteger

numberOfCycles(p) returns the number of non-trivial cycles of the permutation p.

odd?: % -> Boolean

odd?(p) returns true if and only if p is an odd permutation i.e. sign(p) is -1.

one?: % -> Boolean

from MagmaWithUnit

orbit: (%, S) -> Set S

from PermutationCategory S

order: % -> NonNegativeInteger

order(p) returns the order of a permutation p as a group element.

recip: % -> Union(%, failed)

from MagmaWithUnit

rightPower: (%, NonNegativeInteger) -> %

from MagmaWithUnit

rightPower: (%, PositiveInteger) -> %

from Magma

rightRecip: % -> Union(%, failed)

from MagmaWithUnit

sample: %

from MagmaWithUnit

sign: % -> Integer

sign(p) returns the signum of the permutation p, +1 or -1.

smaller?: (%, %) -> Boolean if S has OrderedSet or S has Finite

from Comparable

sort: List % -> List %

sort(lp) sorts a list of permutations lp according to cycle structure first according to length of cycles, second, if S has Finite or S has OrderedSet according to lexicographical order of entries in cycles of equal length.

BasicType

Comparable if S has OrderedSet or S has Finite

Group

Magma

MagmaWithUnit

Monoid

OrderedSet if S has OrderedSet or S has Finite

PartialOrder if S has OrderedSet or S has Finite

SemiGroup

SetCategory

TwoSidedRecip

unitsKnown