, <Duplicate>)combinat::permutations – permutations
The library combinat::permutations provides functions for counting, generating, and manipulating permutations.
Further functions are documented theme by theme in separate help sections:
combinat::permutations::inversions: inversions, Lehmer code, and reduced words of permutations,
combinat::permutations::cycles: cycle decompositions of standard permutations,
combinat::permutations::descents: descents, major indice and major code of permutations,
combinat::permutations::peaks: peaks of permutations,
combinat::permutations::saillances: saillances of permutations,
combinat::permutations::leequalBruhat: Bruhat order on standard permutations,
combinat::permutations::leequalPermutohedron: permutohedron order on standard permutations,
combinat::permutations::hasPattern: patterns of standard permutations.
Superdomain
Categories
Axioms
Related Domains:
Details:
A permutation of a list l is a list of the same size obtained by some reordering of the elements of l.
A standard permutation is a permutation of the list [1,2,...,n], for some positive integer n. For standard permutations, the manipulating functions accept the number n as parameter instead of the list [1,2,...,n].
Several functions accept the option Duplicate. This option specifies whether two reorderings of the elements of l that yield the same list are considered as distinct or not. Hence, without the option Duplicate, the permutations of l are all distinct lists obtained by permuting the elements of l. With the option Duplicate, a list of size n has always exactly n! permutations, which are not necessarily distinct.
Without the option Duplicate, the permutations are generated and listed in lexicographic order.
Entries
|
"domtype" |
The MuPAD domain used to represent permutations: DOM_LIST |
|
"typeStandard" |
The MuPAD type used to represent standard permutations. |
isA – test if an object is a permutation
combinat::permutations::isA(any type perm)
combinat::permutations::isA(any type perm, word wrd)
combinat::permutations::isA(any type perm, nonnegative integer n)
Returns whether perm is a permutation.
Returns whether perm is a permutation of the word wrd.
Returns whether perm is a permutations of the list [1..n].
isAStandard – test if an object is a standard permutation
combinat::permutations::isAStandard(any type perm)
Returns whether perm is a standard permutation.
isStandard – test if a permutation is standard
combinat::permutations::isStandard(permutation perm)
Returns whether perm is a standard permutation.
count – number of permutations
combinat::permutations::count(list , <Duplicate>)
combinat::permutations::count(nonnegative integer n)
Returns the number of permutations of the list l, with or without duplicates.
Returns the number of permutations of the list [1,...,n].
list – list of permutations
combinat::permutations::list(list 
, <Duplicate>)
combinat::permutations::list(nonnegative integer n)
Returns the list of the permutations of the list l, with or without duplicates.
Returns the list of the permutations of the list [1,...,n].
generator – generator for permutations
combinat::permutations::generator(list 
, <Duplicate>)
combinat::permutations::generator(nonnegative integer n)
Returns a generator for the permutations of the list l, with or without duplicates.
Returns a generator for the permutations of the list [1,...,n].
first – first permutation
combinat::permutations::first(list l)
combinat::permutations::first(nonnegative integer n)
Returns the first permutation of the list l in lexicographic order. This is equivalent to sort(l).
Returns the first permutation of the list [1,...,n], that is [1,...,n].
last – last permutation
combinat::permutations::last(list l)
combinat::permutations::last(nonnegative integer n)
Returns the last permutation of the list l in lexicographic order. This is equivalent to revert(sort(l)).
Returns the last permutation of the list [1,...,n], that is [n,...,1].
Next – next permutation
combinat::permutations::Next(numerical list l)
Returns the next permutation of the list l in lexicographic order.
Next cannot deal with duplications, nor with lists whose elements cannot be ordered by <.
previous – previous permutation
combinat::permutations::previous(numerical list l)
Returns the previous permutation of the list l in lexicographic order.
previous can not deal with duplications, nor with lists whose elements cannot be ordered by <.
rank – rank of a permutation
combinat::permutations::rank(standard permutation p)
Returns the rank 
of a permutation p of size 
, this permutation being by definition the 
-th one in the list of all permutations of size 
lexicographically sorted.
rank cannot deal with duplications, nor with lists whose elements cannot be ordered by <.
unrank – unranking of standard permutations
combinat::permutations::unrank(nonnegative integer r, nonnegative integer n)
Returns the permutation of rank 
in the list of standard permutations of size 
lexicographically sorted.
random – random permutation
combinat::permutations::random(list l)
combinat::permutations::random(nonnegative integer n)
Returns a random permutation of the list l.
Returns a random permutation of the list [1,...,n].
inverse – inverse of a standard permutation
combinat::permutations::inverse(standard permutation p)
Returns the inverse of the standard permutation p.
_mult – action and composition of permutations
combinat::permutations::_mult(word w, standard permutation p)
combinat::permutations::_mult(standard permutation p1, standard permutation p2)
Computes the action of the standard permutation p on the word w by permutation of the positions (action on the right).
If p1 is a standard permutation, the result is the composition of p1 and p2 (as 
, p2 acting on the right of p1).
multInverse – Inverse action on positions
combinat::permutations::multInverse(word w, standard permutation p)
combinat::permutations::multInverse(standard permutation p1, standard permutation p2)
Computes the action of the standard permutation p on the word w by inverse permutation of the positions (inverse action on the right).
If p1 is also a standard permutation, the result is the composition of p1 and p2^(-1).
shiftedConcat2 – binary shifted concatenation
combinat::permutations::shiftedConcat2(permutation p1, permutation p2)
Returns the concatenation of p1 with a copy of p2 with all its elements shifted by nops(p1): 
.
The point is that the shifted concatenation of two standard permutations is again a standard permutation.
shiftedConcat – n-ary shifted concatenation
combinat::permutations::shiftedConcat(permutation p1, permutation p2)
The shifted concatenation combinat::permutations::shiftedConcat2 is an associative operation. This function implements the corresponding n-ary operation.
rearrangement – rearrangement of a list
combinat::permutations::rearrangement(list l1, list l2)
Returns a permutation sigma such that l2[sigma[i]]=l[i] if it exists and FAIL otherwise.
toMatrix – permutation matrix of a standard permutation
combinat::permutations::toMatrix(standard permutation p)
Returns the permutation matrix of the standard permutation p seen as an endomorphism of the symmetric group algebra.
Known bug: toMatrix does not work for the trivial permutation [].
Inversions, Lehmer code and reduced words of permutations
An inversion of a permutation 
is a pair of positions 
such that 
and 
. It is represented in MuPAD as a set of two positive integers {i,j}.
The sign of a permutation 
is 
if 
has an odd number of inversions, and 
otherwise.
The Lehmer code of a permutation is the list 
such that 
. where 
denotes the cardinal of the set. Note that 
. The cocode is the list 
such that 
.
A standard permutation is completely determined by its Lehmer code (resp. cocode), and it follows that the Lehmer code provides a bijection between standard permutations of size 
and words 
such that 
(resp 
). If 
is a non standard permutation, then decoding the Lehmer code of 
yields the standardized of 
.
Extending a permutation with fixed points at its end is equivalent to appending zeroes at the end of its Lehmer code. So, the code behaves well with respect to the natural embedding between symmetric groups of different order.
The functions described here only work for permutations whose elements can be ordered by <.
Let 
denote the elementary transposition 
. A word for the permutation 
is a list 
such that 
is equal to the product 
. A word is said to be reduced if it is of minimal length among all the words for the same permutation. The length of a reduced word for 
is equal to the number of inversions of 
. In MuPAD words are represented by lists of positive integers.
inversions – list of the inversions of a permutation
combinat::permutations::inversions(permutation p)
Returns the list of the inversions of the permutation p.
inversionsNumber – number of inversions of a permutation
combinat::permutations::inversionsNumber(permutation p)
Returns the number of inversions of the permutation p.
Complexity: 
, could be 
.
inversionsNumberMerge – number of inversions of a permutation
combinat::permutations::inversionsNumberMerge(permutation p)
Returns the number of inversions of the permutation p.
This method consists in a faster implementation of the combinat::permutations::inversionsNumber method using a modified merge sort algorithm.
Complexity: 
, with bad constant time factor.
sign – sign of a standard permutation
combinat::permutations::sign(standard permutation p)
Returns the sign of the permutation p.
Complexity: 
.
signFromInversionsNumber – sign of a permutation
combinat::permutations::signFromInversionsNumber(permutation p)
Returns the sign of the permutation p, using the number of inversions. The permutation need not be standard.
Complexity: 
, could be 
.
isEven – parity of a standard permutation
combinat::permutations::isEven(permutation p)
Tests if the permutation p is even.
code – Lehmer code of a permutation
combinat::permutations::code(permutation p)
Returns the Lehmer code of the permutation p.
fromCode – standard permutation from its code
combinat::permutations::fromCode(Lehmer code c, <non-negative integer n>)
Recovers the standard permutation of minimal size from the sequence c, appending the minimum necessary number of zeroes to it so that it becomes a Lehmer code.
The argument n, when provided, specifies the size of the returned permutation.
coCode – Lehmer cocode of a permutation
combinat::permutations::coCode(permutation p)
Returns the Lehmer cocode of the permutation p.
reducedWord – Reduced word of a standard permutation
combinat::permutations::reducedWord(permutation p)
Returns a reduced word of the permutation p.
reducedWords – Reduced words of a standard permutation
combinat::permutations::reducedWords(permutation p)
Returns the list of all reduced words of the permutation p.
reducedWordsLexMin – Lexicographically minimal reduced word of a standard permutation
combinat::permutations::reducedWordsLexMin(permutation p)
Returns the Lexicographically minimal reduced word of the permutation p.
fromReducedWord – Standard permutation from a (reduced) word
combinat::permutations::fromReducedWord(reduced word 
, <non-negative integer n>)
Returns the standard permutation of minimal size that is the product of the elementary transpositions represented by w. Note that this word does not need to be reduced.
The argument n, when provided, specifies the size of the returned permutation.
Cycle decomposition of standard permutations
A cycle 
of length 
is the permutation such that 
, and 
for 
. Such a cycle is represented in MuPAD by a list 
. This representation is unique if, for example, c1 is chosen to be minimal.
A cycle of length 
is equal to the identity permutation and is called trivial.
Two disjoint cycles commute.
Any standard permutation 
can be written as a product of disjoint cycles. This is called the cycle decomposition of 
. It is unique up to the order of the cycles, and up to the first element of the cycles.
cycles – cycle decomposition of a standard permutation
combinat::permutations::cycles(standard permutation p)
Returns the cycle decomposition of p. This is the list of the non-trivial cycles of p. Each cycle is represented by the list [i, p[i], p[p[i]], ...] of its elements starting from the smallest one. The cycles themselves are sorted increasingly w.r.t. their first element.
cycleType – cycle type of a standard permutation
combinat::permutations::cycleType(standard permutation p)
Returns the cycle type of the permutation p, as a partition. This is the decreasing list of the lengths of the cycles of p.
fromCycles – standard permutation from its cycle decomposition
combinat::permutations::fromCycles(list of list of integers cycleList, <integer n>)
Returns the standard permutation of minimal size that has the given cycle list. Note that this minimal size corresponds to the greatest element in cycleList.
Trivial cycles of length 1 may be omitted if the greatest element of the permutation is not in a cycle of length 1.
The argument n, when provided, specifies the size of the returned permutation.
fromCycleType – standard permutations with a given cycle type
combinat::permutations::fromCycleType(partitions l)
Returns the list of standard permutations that have cycle type the descent set s. Note that this minimal size corresponds to the greatest element in l.
This is in fact a full-featured combinatorial class, with the usual methods count, generator, list and unrank.
fixedPoints – fixed points of a standard permutation
combinat::permutations::fixedPoints(standard permutation p)
Returns the list of the fixed points of p.
fixedPointsNumber – number of fixed points of a standard permutation
combinat::permutations::fixedPointsNumber(standard permutation p)
Returns the number of fixed points of p.
Descents, major indice and major code of permutations
A descent of a permutation 
is an integer 
such that and 
.
Let 
be the increasing list of the descents of a permutation 
. Let 
be its corresponding composition. We say that 
is the ribbon shape of 
, or, equivalently that 
has 
as ribbon shape.
descents – descents of a permutation
combinat::permutations::descents(permutation p, <FinalDescent>)
Returns the list of the descents of the permutation p, that is, the list of integers 
such that p[i]>p[i+1].
With the option FinalDescent, the last position of a non empty permutation is also considered as a descent.
descentsNumber – number of descents of a permutation
combinat::permutations::descentsNumber(permutation p, <FinalDescent>)
Returns the number of descents of the permutation p.
With the option FinalDescent, the last position of a non empty permutation is also considered as a descent.
majorIndex – major index of a permutation
combinat::permutations::majorIndex(permutation p, <FinalDescent>)
Returns the major index of the permutation p, that is the sum of the descents of p.
With the option FinalDescent, the last position of a non empty permutation is also considered as a descent.
majorCode – major code of a permutation
combinat::permutations::majorCode(permutation p)
Returns the major code of the permutation p, which is defined as the list [m1-m2, m2-m3,..,mn] where mi := maj(pi) is the major indices of the permutation 
obtained by erasing the letters smaller than 
in p.
fromMajorCode – permutation from its major code
combinat::permutations::fromMajorCode(major code c)
Returns the permutations whose major code is p. This is the converse bijection of majorCode.
descentPolynomial – descent polynomial of a permutation
combinat::permutations::descentPolynomial(permutation p, variable z)
Returns the descent polynomial of the permutation p in the variable z. It is the product of the monomials z[p[1]]z[p[2]]...z[p[i]] for all descents i of the permutation p.
Note that the the last position of a non empty permutation is never considered as a descent.
fromDescents – standard permutations with a given descent set
combinat::permutations::fromDescents(list or set s, <integer n>)
Returns the list of standard permutations of minimal size having the descent set s. Note that this minimal size corresponds to the greatest element in s.
The argument n, when provided, specifies the size of the returned permutation.
This is in fact a full-featured combinatorial class, with the usual methods count, generator, list, first, last.
fromDescentsComposition – standard permutations by ribbon shape
combinat::permutations::fromDescentsComposition(composition s)
Returns the list of standard permutations that have ribbon shape s, in lexicographic order.
This is a full-featured combinatorial class, with the usual methods count, generator, list, first, last.
fromDescentsCompositionFiner – standard permutations by finer descents composition
combinat::permutations::fromDescentsCompositionFiner(composition s)
Returns the list of standard permutations whose descent composition is finer than s, in lexicographic order.
This is a full-featured combinatorial class, with the usual methods count, generator, list, first, last.
fromDescentsCompositionFatter – standard permutations by fatter descents composition
combinat::permutations::fromDescentsCompositionFatter(composition s)
Returns the list of standard permutations whose descent composition is finer than s, in lexicographic order.
This is a full-featured combinatorial class, with the usual methods count, generator, list, first, last.
fromRecoilsComposition – standard permutations by recoils composition
combinat::permutations::fromRecoilsComposition(composition s)
Returns the list of standard permutations that have recoil composition s, in lexicographic order.
This is a full-featured combinatorial class, with the usual methods count, generator, list, first, last.
fromRecoilsCompositionFiner – standard permutations by finer recoils composition
combinat::permutations::fromRecoilsCompositionFiner(composition s)
Returns the list of standard permutations whose recoil composition is finer than s, in lexicographic order.
This is a full-featured combinatorial class, with the usual methods count, generator, list, first, last.
fromRecoilsCompositionFatter – standard permutations by fatter recoils composition
combinat::permutations::fromRecoilsCompositionFatter(composition s)
Returns the list of standard permutations whose recoil composition is finer than s, in lexicographic order.
This is a full-featured combinatorial class, with the usual methods count, generator, list, first, last.
descentsToMin – smallest permutation having a given descent set
combinat::permutations::descentsToMin(list or set s, <integer n>)
Returns the standard permutation of minimal size and smallest one with respect to the number of inversions that has the given descent set. Note that this minimal size corresponds to the greatest element in s.
The argument n, when provided, specifies the size of the returned permutation.
This method is deprecated. Please use "fromDescents::first".
descentsToMax – greatest permutation having a given descent set
combinat::permutations::descentsToMax(list or set s, <integer n>)
Returns the standard permutation of minimal size and greatest one with respect to the number of inversions that has the given descent set. Note that this minimal size corresponds to the greatest element in s.
The argument n, when provided, specifies the size of the returned permutation.
This method is deprecated. Please use "fromDescents::last".
descentsCompositionToMin – smallest permutation having a given ribbon shape
combinat::permutations::descentsCompositionToMin(composition s)
Returns the standard permutation of minimal size and smallest one with respect to the number of inversions that has the ribbon shape s. Note that this minimal size corresponds to the sum of the entries of s.
This method is deprecated. Please use "fromDescentsComposition::first".
descentsCompositionToMax – greatest permutation having a given ribbon shape
combinat::permutations::descentsCompositionToMax(composition s)
Returns the standard permutation of minimal size and greatest one with respect to the number of inversions that has the ribbon shape s. Note that this minimal size corresponds to the sum of the entries of s.
This method is deprecated. Please use "fromDescentsComposition::last".
youngSubgroup – Young subgroup
combinat::permutations::youngSubgroup(composition c)
Returns the list of the standard permutations in the Young subgroup (also called parabolic subgroup) 
of the symmetric group 
; otherwise said the standard permutations which stabilize the consecutive intervals 
whose length are given by 
.
Note: combinat::permutations::youngSubgroup is actually a combinatorial class, with the usual list, count and generator methods.
modYoungSubgroup – permutation modulo a Young subgroup
combinat::permutations::modYoungSubgroup(permutation p, composition c)
This returns a canonical representative of p modulo the right action of the Young subgroup 
(see above) on the positions.
This boils down to sorting 
in the consecutive intervals whose lengths are given by 
.
fromSetPartition – permutations stabilizing a standard set partition
combinat::permutations::fromSetPartition(standard set partition setPartition)
setPartition is a set partition of 
, represented by a list of lists or list of sets.
Returns the list of the standard permutations of 
stabilizing each component of setPartition.
Note: combinat::permutations::fromSetPartition is actually a combinatorial class, with the usual list, count and generator methods.
Peaks of permutations
A peak of a permutation 
is an integer 
such that 
and 
.
peaks – peaks of a permutation
combinat::permutations::peaks(permutation p)
Returns the list of the peaks of the permutation p, that is the list of integers 
such that 
and 
.
peaksNumber – number of peaks of a permutation
combinat::permutations::peaksNumber(permutation p)
Returns the number of peaks of the permutation p.
Saillances of permutations
A saillance of a permutation 
is an integer 
such that 
, for all 
.
saillances – saillances of a permutation
combinat::permutations::saillances(permutation p)
Returns the saillances of the permutation p.
This function may be renamed in the future.
saillancesNumber – saillances number of a permutation
combinat::permutations::saillancesNumber(permutation p)
Returns the number of saillances of the permutation p.
This function may be renamed in the future.
Bruhat order on standard permutations
The Bruhat order is a partial order defined on the elements of a given symmetric group, that is, on the permutations of a given size.
A permutation 
is smaller than a permutation 
if and only if one of the reduced words of 
is a subsequence (the chosen letters do not have to be consecutive) of one of the reduced word of 
.
The Bruhat order is the transitive closure of the following relation: 
is smaller than 
if 
is obtained by multiplying 
to the left or to the right by a transposition in such a way that it increases its number of inversions.
leequalBruhat – comparison of two permutations
combinat::permutations::leequalBruhat(standard permutations p1, p2)
Returns the boolean answering the question “Is p1 smaller than p2 in the Bruhat order?”
bruhatInversions – inversions in the Bruhat order
combinat::permutations::bruhatInversions(standard permutation p)
Returns the list of inversions of p such that the application of this inversion to p decrements its number of inversions.
Equivalently, it returns the list of pairs 
, 
such that 
and such that there exists no 
between 
and 
satisfying 
.
predBruhat – predecessors of a permutation
combinat::permutations::predBruhat(standard permutation p)
Returns the list of permutations strictly smaller than p in the Bruhat order, such that there is no permutation between one of those and p.
succBruhat – successors of a permutation
combinat::permutations::succBruhat(standard permutation p)
Returns the list of permutations strictly greater than p in the Bruhat order, such that there is no permutation between p and one of those.
smallerBruhat – permutations smaller than a permutation
combinat::permutations::smallerBruhat(standard permutation p)
Returns the list of permutations smaller than or equal to p in the Bruhat order.
greaterBruhat – permutations greater than a permutation
combinat::permutations::greaterBruhat(standard permutation p)
Returns the list of permutations greater than or equal to p in the Bruhat order.
Permutohedron order on standard permutations
The permutohedron order is a partial order defined on the elements of a given symmetric group, that is, on the permutations of a given size. It is also known under the name of “weak Bruhat order”.
There are two different orders whether one make the permutations act to the left or to the right on the symmetric group. By default, computations are done in the right permutohedron.
A permutation 
is smaller than a permutation 
in the left (resp. right) permutohedron if and only if any reduced word of 
is a suffix (resp. prefix) of one of the reduced word of 
.
Equivalently, 
is smaller than 
in the left (resp. right) permutohedron if and only if one can go from 
to 
by multiplying 
on the left (resp. right) by a sequence of elementary transpositions that increment at each step its number of inversions.
leequalPermutohedron – comparison of two permutations
combinat::permutations::leequalPermutohedron(standard permutations p1, p2, <Left | Right>)
Returns the boolean answering the question “Is p1 smaller than p2 in the permutohedron order?”
With no option given or with the option Right, computations are done in the right permutohedron. With the option Left, computations are done in the left permutohedron.
predPermutohedron – predecessors of a permutation
combinat::permutations::predPermutohedron(standard permutation p, <Left | Right>)
Returns the list of permutations strictly smaller than p in the permutohedron order, such that there is no permutation between one of those and p.
With no option given or with the option Right, computations are done in the right permutohedron. With the option Left, computations are done in the left permutohedron.
succPermutohedron – successors of a permutation
combinat::permutations::succPermutohedron(standard permutation p, <Left | Right>)
Returns the list of permutations strictly greater than p in the permutohedron order, such that there is no permutation between p and one of those.
With no option given or with the option Right, computations are done in the right permutohedron. With the option Left, computations are done in the left permutohedron.
smallerPermutohedron – permutations smaller than a permutation
combinat::permutations::smallerPermutohedron(standard permutation p, <Left | Right>)
Returns the list of permutations smaller than or equal to p in the permutohedron order.
With no option given or with the option Right, computations are done in the right permutohedron. With the option Left, computations are done in the left permutohedron.
greaterPermutohedron – permutations greater than a permutation
combinat::permutations::greaterPermutohedron(standard permutation p, <Left | Right>)
Returns the list of permutations greater than or equal to p in the permutohedron order.
With no option given or with the option Right, computations are done in the right permutohedron. With the option Left, computations are done in the left permutohedron.
Patterns of standard permutations
A permutation 
of size 
avoids the pattern 
of size 
if and only if there is no subsequence 
in 
such that 
.
hasPattern – test of the existence of a pattern in a standard permutation
combinat::permutations::hasPattern(standard permutations perm, patt)
Returns the boolean answering the question “Is patt a pattern appearing in perm?”
patternPositions – positions of a pattern in a permutation
combinat::permutations::patternPositions(standard permutations perm, patt)
Returns the list of positions where the pattern patt appears in the standard permutations perm.
There are 
permutations of the list [a,b,c]:
combinat::permutations::count([a, b, c])
Here is the list:
combinat::permutations::list([a, b, c])
For the permutations of [1,2,3], it is shorter to write:
combinat::permutations::count(3);
combinat::permutations::list(3);
You can use the function combinat::permutations::first to get the “first” permutation of a list or the first standard permutation of a given size:
combinat::permutations::first([c, b, a, d]);
combinat::permutations::first(4)
Using combinat::permutations::Next, you can calculate the “next” permutation. This function takes as argument the permutation relative to which you want the next one:
combinat::permutations::Next([1, 3, 2, 4])
combinat::permutations::Next returns FAIL when the input is the last permutation:
combinat::permutations::Next([4, 3, 2, 1])
You can also go backward with combinat::permutations::last and combinat::permutations::previous
combinat::permutations::last([1, 2, 3, 4]);
combinat::permutations::previous([1, 3, 2, 4]);
When you want to run through the permutations of a list, you can generate them one by one to save memory:
g := combinat::permutations::generator(3):
g();
g(), g(), g(), g(), g(), g();
h := combinat::permutations::generator([c, a, b]):
h();
h(), h(), h(), h(), h(), h();
Typically, this would be used as follows:
g := combinat::permutations::generator(3):
while (p := g()) <> FAIL do print(p): end:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
By default, the permutations of a given list are all distinct lists obtained by permuting its elements:
combinat::permutations::count([a, a, b]);
combinat::permutations::list([a, a, b]);
To consider reorderings with multiplicities, one can use the Duplicate option:
combinat::permutations::count([a, a, b], Duplicate);
combinat::permutations::list([a, a, b], Duplicate);
Note that with the option Duplicate as above, the permutations are not guaranted to be listed in lexicographic order.
You can get the rank of a permutation using:
combinat::permutations::rank([3, 6, 5, 4, 2, 1]);
Conversely, you can recover the permutation of rank 
and size 
using:
combinat::permutations::unrank(360,6);
Here is the way to get a random permutation:
combinat::permutations::random([a,a,b,c,d,d,e,f]);
combinat::permutations::random(10);
In this example, we show how to use some natural associative operations on permutations.
The shifted concatenation is a variant on the usual concatenation of words which preserves standard permutations by shifting appropriately the elements of the second operand:
combinat::permutations::shiftedConcat2([1,2,3], [1,2])
combinat::permutations::shiftedConcat2([3,2,1], [2,1])
This binary operation is in fact associative; here is the n-ary version of it:
combinat::permutations::shiftedConcat([3,2,1], [2,1], [1,2,3])
and the unit of this operation is the emtpy permutation:
combinat::permutations::shiftedConcat()
It is sometimes useful to represent a standard permutation by its matrix:
combinat::permutations::toMatrix([2, 4, 1, 5, 3]);
The inverse permutation is computed by:
combinat::permutations::inverse([2, 4, 1, 5, 3])
It corresponds to the transpose matrix:
combinat::permutations::toMatrix(
combinat::permutations::inverse([2,4,1, 5, 3])),
linalg::transpose(
combinat::permutations::toMatrix([2,4, 1, 5, 3]))
The number of inversions of a permutation, also called its length, can be computed with:
combinat::permutations::inversionsNumber([1, 2, 6, 4, 7, 3, 5])
Here is the list of the 
inversions of the previous permutation:
combinat::permutations::inversions([1, 2, 6, 4, 7, 3, 5])
Note that this also works for non-standard permutations, as long as the elements can be ordered with <:
combinat::permutations::inversionsNumber([1, 3, 2, 1, 2, 1]);
combinat::permutations::inversions([1, 3, 2, 1, 2, 1]);
combinat::permutations::inversions(["c", "b", "a"])
The sign of any transposition is 
:
combinat::permutations::sign([4, 2, 3, 1, 5])
Furthermore, the sign defines a multiplicative morphism from the symmetric group into 
. We check this for the symmetric group of order 
:
bool(_and(combinat::permutations::sign(combinat::permutations::_mult(p,q))
= combinat::permutations::sign(p)*combinat::permutations::sign(q)
$ p in combinat::permutations(4)
$ q in combinat::permutations(4)))
The code provides a bijection between permutations of [$1..n] and lists c of length n such that c[i]<=n-i:
for p in combinat::permutations(3) do
code := combinat::permutations::code(p);
p2 := combinat::permutations::fromCode(code);
print(p, code, p2);
end_for
[1, 2, 3], [0, 0, 0], [1, 2, 3]
[1, 3, 2], [0, 1, 0], [1, 3, 2]
[2, 1, 3], [1, 0, 0], [2, 1, 3]
[2, 3, 1], [1, 1, 0], [2, 3, 1]
[3, 1, 2], [2, 0, 0], [3, 1, 2]
[3, 2, 1], [2, 1, 0], [3, 2, 1]
If 
is a non standard permutation, then decoding the code of 
yields the standardized of 
:
w := [2, 3, 1, 2, 2, 4, 5, 1]:
code := combinat::permutations::code(w);
combinat::words::standard(w), combinat::permutations::fromCode(code)
The permutation corresponding to a given product of elementary transpositions can be computed with:
combinat::permutations::fromReducedWord([3,2,3,1,2,3,1]);
The word we entered previously is not reduced. Indeed, all reduced words of a given permutation have the same length, equal to the number of inversions of [3, 4, 2, 1]. It is not the case of the product we studied before.
map(combinat::permutations::reducedWords([3,4,2,1]),nops);
nops([3,2,3,1,2,3,1]);
If you have an action of the symmetric group on a set, defined by the action of the elementary transpositions, you can compute a reduced decomposition of a given permutation with:
combinat::permutations::reducedWord([3,5,4,6,2,1]);
The cycles of a permutation can be computed with:
combinat::permutations::cycles([3,5,1,2,4]);
You can recover the initial permutation by two different ways, forgetting or not the cycle of length 
:
combinat::permutations::fromCycles([[1, 3], [2, 5], [4]]),
combinat::permutations::fromCycles([[1, 3], [2, 5]]);
You can generate the list of permutations with a given cycle type, which is a conjugacy class of the symmetric group, and then check that their number corresponds to the usual formula:
select(combinat::permutations::list(4),
z-> combinat::permutations::cycleType(z)=[2,2]);
nops(%), 4!/(2^2*2!);
To compute the list or the number of fixed points of a permutation, you can use:
combinat::permutations::fixedPoints([6, 7, 3, 8, 5, 9, 2, 1, 4]);
combinat::permutations::fixedPointsNumber([6, 7, 3, 8, 5, 9, 2, 1, 4]);
It can be used to quickly get an estimation of the number of permutations without fixed points, using the following main block inside a loop, and check the hats paradox:
combinat::permutations::fixedPoints(combinat::permutations::random(20));
[13]
The descents of a permutation are computed as:
combinat::permutations::descents([2, 1, 6, 4, 7, 3, 5])
The sum of the descents is called the major index:
combinat::permutations::majorIndex([2, 1, 6, 4, 7, 3, 5])
It is the total degree of the descent polynomial, that is always a monomial on permutations:
combinat::permutations::descentPolynomial([2, 1, 6, 4, 7, 3, 5],z)
We compute the major code of a permutation:
combinat::permutations::majorCode([2, 1, 6, 4, 7, 3, 5])
The sum of the major code is the major index:
combinat::permutations::majorIndex([2, 1, 6, 4, 7, 3, 5])
One can retrieve a permutations knowing its major code:
combinat::permutations::fromMajorCode([3, 2, 0, 2, 2, 0, 0])
To compute the smallest element of a descent class, you can use:
combinat::permutations::fromDescents::first([2, 1, 5, 9], 12)
To get the same result using ribbon shapes, one can write:
combinat::permutations::fromDescentsComposition::first([1, 1, 3, 4, 3])
To compute the greatest element of a descent class, you can use:
combinat::permutations::fromDescents::last([2, 1, 5, 9], 12)
To get the same result using ribbon shapes, one can write:
combinat::permutations::fromDescentsComposition::last([1, 1, 3, 4, 3])
To compute the list of permutations that have a given descent set, you can use:
combinat::permutations::fromDescents([3, 5, 1])
To get the same result using ribbon shapes, one can write:
combinat::permutations::fromDescentsComposition([1, 2, 2])
Here are all the permutations in the Young subgroup 
:
combinat::permutations::youngSubgroup([2, 3])
Taking canonical representative of the orbit of words w.r.t. the action of this Young subgroup on positions is trivial; it suffices to sort the two first and the last three letters:
combinat::permutations::modYoungSubgroup([c, b, e, a, d], [2, 3])
The peaks of a permutation are computed as:
combinat::permutations::peaks([2, 1, 6, 4, 7, 3, 5])
The number of peaks can be directly computed using:
combinat::permutations::peaksNumber([2, 1, 6, 4, 7, 3, 5])
The saillances of a permutation are computed as:
combinat::permutations::saillances([7, 1, 4, 6, 2, 5, 3]);
The number of saillances can be directly computed using:
combinat::permutations::saillancesNumber([7, 1, 4, 6, 2, 5, 3]);
To check whether a permutation is smaller than another thanks to the Bruhat order, you can call:
combinat::permutations::leequalBruhat([2,4,3,1],[3,4,2,1]);
You can ask for the inversions of a given permutation by:
combinat::permutations::bruhatInversions([6, 1, 4, 5, 2, 3])
Applying those inversions to the previous permutation, you exactly get the permutations preceding it as you can check with
combinat::permutations::predBruhat([6, 1, 4, 5, 2, 3])
Now, you can compute the transitive ideal generated by the predecessor relation and get (on the previous example, the answer is one page long)
combinat::permutations::smallerBruhat([4, 1, 2, 3])
What was done with the permutations preceding a given one or smaller than it, can also be performed by the permutations succeeding a given one or greater than it by:
combinat::permutations::succBruhat([6, 1, 4, 5, 2, 3]);
combinat::permutations::greaterBruhat([4, 1, 2, 3])
All the computations in this example are done in the right permutohedron. To check whether a permutation is smaller than another thanks to the permutohedron order, you can use:
combinat::permutations::leequalPermutohedron([3,2,1,4],[4,2,1,3]);
To compute what permutations precede a given permutation, you can use:
combinat::permutations::predPermutohedron([4, 2, 1, 3]);
Now, you can compute the transitive ideal generated by the predecessor relation and get:
combinat::permutations::smallerPermutohedron([4, 2, 1, 3]);
What was done with the permutations preceding a given one or smaller than it, can also be performed by the permutations succeeding a given one or greater than it by:
combinat::permutations::succPermutohedron([4, 2, 1, 3]);
combinat::permutations::greaterPermutohedron([4, 2, 1, 3]);
All the computations in this example are done in the left permutohedron. All the result can be compared with the results of the previous example. To check whether a permutation is smaller than another thanks to the permutohedron order, you can use:
combinat::permutations::leequalPermutohedron([3,2,1,4],[4,2,1,3],Left);
To compute what permutations precede a given permutation in the left permutohedron, you can use:
combinat::permutations::predPermutohedron([4, 2, 1, 3], Left);
Now, you can compute the transitive ideal generated by the predecessor relation in the left permutohedron and get:
combinat::permutations::smallerPermutohedron([4, 2, 1, 3], Left);
What was done with the permutations preceding a given one or smaller than it, can also be performed by the permutations succeeding a given one or greater than it by:
combinat::permutations::succPermutohedron([4, 2, 1, 3], Left);
combinat::permutations::greaterPermutohedron([4, 2, 1, 3], Left);
To check whether a permutation contains a given pattern, you can use:
combinat::permutations::hasPattern([3, 5, 1, 4, 6, 2], [1, 3, 2])
To look at the positions where the pattern appears, you can ask:
combinat::permutations::patternPositions([3, 5, 1, 4, 6, 2], [1, 3, 2])
