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 pages:
combinat::permutations::inversions
,
combinat::permutations::cycles
,
combinat::permutations::descents
.
combinat::permutations::leequalBruhat
.
combinat::permutations::leequalPermutoedron
.
combinat::permutations::peaks
.
combinat::permutations::saillances
.
combinat::permutations::haspattern
.
l
is a list of the same
size obtained by some reordering of the elements of l
.[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]
.l
that are 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
exactly has n!
permutations, that are not necessarily distinct lists.Cat::CombinatorialClass
The MuPAD domain used to represent permutations: DOM_LIST
The MuPAD type used to represent standard permutations.
isA(any type perm)
perm
is a permutations.isA(any type perm, word wrd)
perm
is a permutations of the word wrd
.isA(any type perm, nonnegative integer n)
perm
is a permutations of the list [1..n]
.
isAStandard(any type perm)
perm
is a standard permutations.
count(list l <, Duplicate>)
l
, with
or without duplicates.count(nonnegative integer n)
[1,...,n]
.
list(list l <, Duplicate>)
l
, with
or without duplicates.list(nonnegative integer n)
[1,...,n]
.
generator(list l <, Duplicate>)
l
,
with or without duplicates.generator(nonnegative integer n)
[1,...,n]
.
first(list l)
l
in
lexicographic order. This is equivalent to sort(l)
.first(nonnegative integer n)
[1,...,n]
, that
is [1,...,n]
.
last(list l)
l
in
lexicographic order. This is equivalent to revert(sort(l))
.last(nonnegative integer n)
[1,...,n]
, that
is [n,...,1]
.
Next(numerical list l)
l
in
lexicographic order.Next
cannot deal with duplications, nor with lists whose
elements cannot be ordered by <
.
previous(numerical list l)
l
in
lexicographic order.previous
can not deal with duplications, nor with lists whose
elements cannot be ordered by <
.
rank(standard permutation p)
p
of size n, this
permutation being by definition the r-th one in the list of all
permutations of size n lexicographically sorted.rank
cannot deal with duplications, nor with lists whose
elements cannot be ordered by <
.
unrank(nonnegative integer r, nonnegative integer n)
random(list l)
l
.random(nonnegative integer n)
[1,...,n]
.
inverse(standard permutation p)
p
.
_mult(word w, standard permutation p)
_mult(standard permutation p1, standard permutation p2)
p
on the word
w
(action on the right). If p1
is a standard permutation, it
performs the composition of p1
and p2
(as p1 p2,
p2
acting on the right of p1
).
toMatrix(standard permutation p)
p
seen as an endomorphism of the symmetric group algebra.toMatrix
does not work for the trivial
permutation []
.There are 6 permutations of the list [a,b,c]
:
>> combinat::permutations::count([a, b, c])
6
Here is the list:
>> combinat::permutations::list([a, b, c])
[[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b], [c, b, a]]
For the permutations of [1,2,3]
, it is shorter to write:
>> combinat::permutations::count(3);
combinat::permutations::list(3);
6 [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
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)
[a, b, c, d] [1, 2, 3, 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])
[1, 3, 4, 2]
combinat::permutations::Next
returns FAIL
when the
input is the last permutation:
>> combinat::permutations::Next([4, 3, 2, 1])
FAIL
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]);
[4, 3, 2, 1] [1, 2, 4, 3]
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();
[1, 2, 3] [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1], FAIL [a, b, c] [a, c, b], [b, a, c], [b, c, a], [c, a, b], [c, b, a], FAIL
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]);
3 [[a, a, b], [a, b, a], [b, a, a]]
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);
6 [[a, a, b], [a, b, a], [a, a, b], [a, b, a], [b, a, a], [b, a, a]]
Note that with the option Duplicateas 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]);
360
Conversely, you can recover the permutation of rank r and size n using:
>> combinat::permutations::unrank(360,6);
[3, 6, 5, 4, 2, 1]
Here is the way to get a random permutation:
>> combinat::permutations::random([a,a,b,c,d,d,e,f]);
combinat::permutations::random(10);
[d, b, c, f, e, a, d, a] [8, 1, 2, 6, 4, 9, 7, 10, 3, 5]
It is sometime useful to represent a standard permutation by its matrix:
>> combinat::permutations::toMatrix([2, 4, 1, 5, 3]);
+- -+ | 0, 0, 1, 0, 0 | | | | 1, 0, 0, 0, 0 | | | | 0, 0, 0, 0, 1 | | | | 0, 1, 0, 0, 0 | | | | 0, 0, 0, 1, 0 | +- -+
The inverse permutation is computed by:
>> combinat::permutations::inverse([2, 4, 1, 5, 3])
[3, 1, 5, 2, 4]
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]))
+- -+ +- -+ | 0, 1, 0, 0, 0 | | 0, 1, 0, 0, 0 | | | | | | 0, 0, 0, 1, 0 | | 0, 0, 0, 1, 0 | | | | | | 1, 0, 0, 0, 0 |, | 1, 0, 0, 0, 0 | | | | | | 0, 0, 0, 0, 1 | | 0, 0, 0, 0, 1 | | | | | | 0, 0, 1, 0, 0 | | 0, 0, 1, 0, 0 | +- -+ +- -+
MuPAD Combinat, an open source algebraic combinatorics package