# Permutation S¶

perm.spad line 43 [edit on github]

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

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

- <: (%, %) -> Boolean
from PermutationCategory S

- >=: (%, %) -> 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

- 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

- 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

- 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