# Permutation SΒΆ

- S: SetCategory

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
- from PermutationCategory S
- <=: (%, %) -> Boolean if S has OrderedSet or S has Finite
- from PartialOrder
- =: (%, %) -> 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
- from CoercibleTo 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)`

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

Comparable if S has OrderedSet or S has Finite

OrderedSet if S has OrderedSet or S has Finite

PartialOrder if S has OrderedSet or S has Finite