# 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`.

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