% $Id: permutations.tex,v 1.1.1.8 2004/10/21 15:52:50 nthiery Exp $
\begin{Mhelppage}{permutations}{F.~Hivert and N.~Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
\Mproofread{Nicolas M. Thiéry}{23/10/2002}{}
\Mproofread{JC Novelli}{10/2004}{}

\begin{MInfo}
  \eng{permutations}
\end{MInfo}

\MDeclareOption{\Duplicate}{Duplicate}

\begin{MIntro}
  \eng{The library \Mthis{} provides functions for counting,
    generating, and manipulating permutations.}
  \eng{Further functions are documented theme by theme in separate help
    sections:
  % FIXME: use cross references to the sections themselves,
  % not to functions inside those sections
  \begin{itemize}
  \item inversions and code of permutations
    \Mup{combinat::permutations::inversions},
  \item cycle decompositions of permutations
    \Mup{combinat::permutations::cycles},
  \item descents set of permutations
    \Mup{combinat::permutations::descents}.
  \item Bruhat order \Mup{combinat::permutations::leequalBruhat}.
  \item permutohedron order \Mup{combinat::permutations::leequalPermutohedron}.
  \item peaks of permutations \Mup{combinat::permutations::peaks}.
  \item saillances of permutations
    \Mup{combinat::permutations::saillances}.
  \item patterns in permutations
    \Mup{combinat::permutations::hasPattern}.
%  \item connected permutations
%    \Mup{combinat::permutations::isConnected}.
  \end{itemize}}
\end{MIntro}

\MKeywords{combinatorics,permutations}

\begin{MDetails}
  \eng{A \emph{permutation} of a list \Mpar{l} is a list of the same
    size obtained by some reordering of the elements of \Mpar{l}.}
  
  \eng{A \emph{standard permutation} is a permutation of the list
    \Mpar{[1,2,...,n]}, for some positive integer \Mpar{n}. For
    standard permutations, the manipulating functions accept the
    number \Mpar{n} as parameter instead of the list
    \Mpar{[1,2,...,n]}.}

  \eng{Several functions accept the option \Duplicate. This option
    specifies whether two reorderings of the elements of \Mpar{l}
    that are the same list are considered as distinct or not.
    Hence, without the option \Duplicate, the permutations of \Mpar{l}
    are all distinct lists obtained by permuting the elements of \Mpar{l}.
    With the option \Duplicate, a list of size \Mex{n} exactly has \Mex{n!}
    permutations, that are not necessarily distinct lists.}
  
  \eng{Without the option \Duplicate, the permutations are generated
    and listed in lexicographic order.}
\end{MDetails}

\begin{MCategories}
\Mup{Cat::CombinatorialClass}
\end{MCategories}

\MRelatedDomains{combinat::words}

\begin{MDomEntries}
  \MDomEntry{domtype}
  \eng{The \mupad\ domain used to represent permutations: \Mup{DOM_LIST}}
  \MDomEntry{typeStandard}
  \eng{The \mupad\ type used to represent standard permutations.}
\end{MDomEntries}

\begin{MMethodDetails}{isA}
  \infoEng{test if an object is a permutations}
  \call{\Mtype{any type} perm}
  \eng{Returns whether \Mpar{perm} is a permutations.}
  \call{\Mtype{any type} perm, \Mtype{word} wrd}
  \eng{Returns whether \Mpar{perm} is a permutations of the word \Mpar{wrd}.}
  \call{\Mtype{any type} perm, \Mtype{nonnegative integer} n}
  \eng{Returns whether \Mpar{perm} is a permutations of the list \Mex{[1..n]}.}
\end{MMethodDetails}

\begin{MMethodDetails}{isAStandard}
  \infoEng{test if an object is a standard permutations}
  \call{\Mtype{any type} perm}
  \eng{Returns whether \Mpar{perm} is a standard permutations.}
\end{MMethodDetails}

\begin{MMethodDetails}{isStandard}
  \infoEng{test if a permutation is standard}
  \call{\Mtype{permutation} perm}
  \eng{Returns whether \Mpar{perm} is a standard permutations.}
\end{MMethodDetails}

\begin{MMethodDetails}{count}
  \infoEng{number of permutations}
  \call{\Mtype{list} l \Mopt{, Duplicate}}%
  \eng{Returns the number of permutations of the list \Mpar{l}, with
    or without duplicates.}
  \call{\Mtype{nonnegative integer} n}%
  \eng{Returns the number of permutations of the list \Mex{[1,...,n]}.}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of the permutations}
  \call{\Mtype{list} l \Mopt{, Duplicate}}%
  \eng{Returns the list of the permutations of the list \Mpar{l}, with
    or without duplicates.}
  \call{\Mtype{nonnegative integer} n}%
  \eng{Returns the list of the permutations of the list \Mex{[1,...,n]}.}
\end{MMethodDetails}

\begin{MMethodDetails}{generator}
  \infoEng{generator for permutations}
  \call{\Mtype{list} l \Mopt{, Duplicate}}%
  \eng{Returns a generator for the permutations of the list \Mpar{l},
    with or without duplicates.}
  \call{\Mtype{nonnegative integer} n}%
  \eng{Returns a generator for the permutations of the list \Mex{[1,...,n]}.}
\end{MMethodDetails}

\begin{MMethodDetails}{first}
  \infoEng{first permutation}
  \call{\Mtype{list} l}%
  \eng{Returns the first permutation of the list \Mpar{l} in
    lexicographic order. This is equivalent to \Mex{sort(l)}.}
  \call{\Mtype{nonnegative integer} n}%
  \eng{Returns the first permutation of the list \Mex{[1,...,n]}, that
    is \Mex{[1,...,n]}.}
\end{MMethodDetails}

\begin{MMethodDetails}{last}
  \infoEng{last permutation}
  \call{\Mtype{list} l}%
  \eng{Returns the last permutation of the list \Mpar{l} in
    lexicographic order. This is equivalent to \Mex{revert(sort(l))}.}
  \call{\Mtype{nonnegative integer} n}%
  \eng{Returns the last permutation of the list \Mex{[1,...,n]}, that
    is \Mex{[n,...,1]}.}
\end{MMethodDetails}

\begin{MMethodDetails}{Next}
  \infoEng{next permutation}
  \call{\Mtype{numerical list} l}%
  \eng{Returns the next permutation of the list \Mpar{l} in
    lexicographic order.}
  \eng{\Mex{Next} cannot deal with duplications, nor with lists whose
    elements cannot be ordered by \Mup{<}.}
\end{MMethodDetails}

\begin{MMethodDetails}{previous}
  \infoEng{previous permutation}
  \call{\Mtype{numerical list} l}%
  \eng{Returns the previous permutation of the list \Mpar{l} in
    lexicographic order.}
  \eng{\Mex{previous} can not deal with duplications, nor with lists whose
    elements cannot be ordered by \Mup{<}.}
\end{MMethodDetails}

\begin{MMethodDetails}{rank}
  \infoEng{rank of a permutation}
  \call{\Mtype{standard permutation} p}%
  \eng{Returns the rank $r$ of a permutation \Mpar{p} of size $n$, this
    permutation being by definition the $r$-th one in the list of all
    permutations of size $n$ lexicographically sorted.}
  \eng{\Mex{rank} cannot deal with duplications, nor with lists whose
    elements cannot be ordered by \Mup{<}.}
\end{MMethodDetails}

\begin{MMethodDetails}{unrank}
  \infoEng{permutation unranked}
  \call{\Mtype{nonnegative integer} r, \Mtype{nonnegative integer} n}%
  \eng{Returns the permutation of rank $r$ in the list of standard
    permutations of size $n$ lexicographically sorted.}
\end{MMethodDetails}

\begin{MMethodDetails}{random}
  \infoEng{random permutation}
  \call{\Mtype{list} l}%
  \eng{Returns a random permutation of the list \Mpar{l}.}
  \call{\Mtype{nonnegative integer} n}%
  \eng{Returns a random permutation of the list \Mex{[1,...,n]}.}
\end{MMethodDetails}

\begin{MMethodDetails}{inverse}
  \infoEng{inverse of a standard permutation}
  \call{\Mtype{standard permutation} p}
  \eng{Returns the inverse of the standard permutation \Mpar{p}.}
\end{MMethodDetails}

\begin{MMethodDetails}{_mult}
  \infoEng{Action and composition of permutations}
  \call{\Mtype{word} w, \Mtype{standard permutation} p}
  \call{\Mtype{standard permutation} p1, \Mtype{standard permutation} p2}
  \eng{Computes the action of the standard permutation \Mpar{p} on the
    word \Mpar{w} by permutation of the positions (action on the
    right).}
  \eng{If \Mpar{p1} is a standard permutation, the result is the
    composition of \Mpar{p1} and \Mpar{p2} (as $p1\circ p2$, \Mpar{p2}
    acting on the right of \Mpar{p1}).}
\end{MMethodDetails}

\begin{MMethodDetails}{multInverse}[ImplState=beta,TestState=beta,DocState=beta]
  \infoEng{Inverse action of permutations}
  \call{\Mtype{word} w, \Mtype{standard permutation} p}
  \call{\Mtype{standard permutation} p1, \Mtype{standard permutation} p2}
  \eng{Computes the action of the standard permutation \Mpar{p} on the
    word \Mpar{w} by inverse permutation of the positions (inverse
    action on the right).}
  \eng{If \Mpar{p1} is also a standard permutation, the result is the
    composition of \Mpar{p1} and \Mex{p2^-1}.}
\end{MMethodDetails}

\begin{MMethodDetails}{toMatrix}
  \infoEng{permutation matrix of a standard permutation}
  \call{\Mtype{standard permutation} p}%
  \eng{Returns the permutation matrix of the standard permutation
    \Mpar{p} seen as an endomorphism of the symmetric group algebra.}%
  \eng{Known bug: \Mex{toMatrix} does not work for the trivial
    permutation \Mex{[]}.}
\end{MMethodDetails}

%% Florent: removed from the interface. Use hasPatterns instead
%% \begin{MMethodDetails}{has1324}
%%   \infoEng{test for pattern 1324}
%%   \call{\Mtype{standard permutation} p}%
%%   \eng{Returns whether the permutation \Mpar{p} contains the pattern 1324.}
%% \end{MMethodDetails}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Examples %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{MExample}{permutation-basic}
  \eng{There are $6$ permutations of the list \Mex{[a,b,c]}:}
  \begin{Mexin}
combinat::permutations::count([a, b, c])
  \end{Mexin}
  \begin{Mexout}
                               6
  \end{Mexout}
  \eng{Here is the list:}
  \begin{Mexin}
combinat::permutations::list([a, b, c])
  \end{Mexin}
  \begin{Mexout}
[[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b],

   [c, b, a]]
  \end{Mexout}
  \eng{For the permutations of \Mex{[1,2,3]}, it is shorter to write:}
  \begin{Mexin}
combinat::permutations::count(3);
combinat::permutations::list(3);
  \end{Mexin}
  \begin{Mexout}
                               6

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2],

   [3, 2, 1]]
  \end{Mexout}
  
  \eng{You can use the function \Mex{combinat::permutations::first} to
    get the ``first'' permutation of a list or the first standard
    permutation of a given size:}
  \begin{Mexin}
combinat::permutations::first([c, b, a, d]);
combinat::permutations::first(4)
  \end{Mexin}
  \begin{Mexout}
                         [a, b, c, d]

                         [1, 2, 3, 4]
  \end{Mexout}
 
  \eng{Using \Mex{combinat::permutations::Next}, you can calculate the
    ``next'' permutation.  This function takes as argument the permutation
    relative to which you want the next one:}
  \begin{Mexin}
combinat::permutations::Next([1, 3, 2, 4])
  \end{Mexin}
  \begin{Mexout}
                         [1, 3, 4, 2]
  \end{Mexout}  
  \eng{\Mex{combinat::permutations::Next} returns \Mup{FAIL} when the
    input is the last permutation:}
  \begin{Mexin}
combinat::permutations::Next([4, 3, 2, 1])
  \end{Mexin}
  \begin{Mexout}
                             FAIL
  \end{Mexout}

  \eng{\begin{sloppypar}
    You can also go backward with
    \Mex{combinat::permutations::last} and
    \Mex{combinat::permutations::previous}
    \end{sloppypar}}
  \begin{Mexin}
combinat::permutations::last([1, 2, 3, 4]);    
combinat::permutations::previous([1, 3, 2, 4]);    
  \end{Mexin}
  \begin{Mexout}
                         [4, 3, 2, 1]

                         [1, 2, 4, 3]
  \end{Mexout}

  \eng{When you want to run through the permutations of a list, you
    can generate them one by one to save memory:}
  \begin{Mexin}
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();
  \end{Mexin}
  \begin{Mexout}
                           [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
  \end{Mexout}

  \eng{Typically, this would be used as follows:}
  \begin{Mexin}
g := combinat::permutations::generator(3):
while (p := g()) <> FAIL do print(p): end:
  \end{Mexin}
  \begin{Mexout}
                           [1, 2, 3]

                           [1, 3, 2]

                           [2, 1, 3]

                           [2, 3, 1]

                           [3, 1, 2]

                           [3, 2, 1]
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-duplicate}
  \eng{By default, the permutations of a given list are all distinct lists
    obtained by permuting its elements:}
  \begin{Mexin}
combinat::permutations::count([a, a, b]);
combinat::permutations::list([a, a, b]);
  \end{Mexin}
  \begin{Mexout}
                               3
                               
               [[a, a, b], [a, b, a], [b, a, a]]
  \end{Mexout}
  \eng{To consider reorderings with multiplicities, one can use the
    \Duplicate\ option:}
  \begin{Mexin}
combinat::permutations::count([a, a, b], Duplicate);
combinat::permutations::list([a, a, b], Duplicate);
  \end{Mexin}
  \begin{Mexout}
                               6

[[a, a, b], [a, b, a], [a, a, b], [a, b, a], [b, a, a],

   [b, a, a]]
  \end{Mexout}
  \eng{Note that with the option \Duplicate as above, the permutations
    are not guaranted to be listed in lexicographic order.}
\end{MExample}

\begin{MExample}{ex-rank}
  \eng{You can get the rank of a permutation using:}
  \begin{Mexin}
combinat::permutations::rank([3, 6, 5, 4, 2, 1]);
  \end{Mexin}
  \begin{Mexout}
                              360
  \end{Mexout}
  \eng{Conversely, you can recover the permutation of rank $r$ and size $n$
    using:}
  \begin{Mexin}
combinat::permutations::unrank(360,6);
  \end{Mexin}
  \begin{Mexout}
                      [3, 6, 5, 4, 2, 1]
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-rand}
  \eng{Here is the way to get a random permutation:}
  \begin{Mvin}{test=false}
combinat::permutations::random([a,a,b,c,d,d,e,f]);
combinat::permutations::random(10);
  \end{Mvin}
  \begin{Mvout}{test=false}
                   [d, b, c, f, e, a, d, a]

                [8, 1, 2, 6, 4, 9, 7, 10, 3, 5]
  \end{Mvout}
\end{MExample}

\begin{MExample}{ex-mat-inverse}
  \eng{It is sometime useful to represent a standard permutation by
    its matrix:}
  \begin{Mexin}
combinat::permutations::toMatrix([2, 4, 1, 5, 3]);    
  \end{Mexin}
  \begin{Mexout}  
                      +-               -+
                      |  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  |
                      +-               -+
  \end{Mexout}

  \eng{The inverse permutation is computed by:}
  \begin{Mexin}
combinat::permutations::inverse([2, 4, 1, 5, 3])    
  \end{Mexin}
  \begin{Mexout}  
                        [3, 1, 5, 2, 4]
  \end{Mexout}
  \eng{It corresponds to the transpose matrix:}
  \begin{Mexin}
combinat::permutations::toMatrix(
   combinat::permutations::inverse([2,4,1, 5, 3])),
linalg::transpose(
   combinat::permutations::toMatrix([2,4, 1, 5, 3]))
  \end{Mexin}
  \begin{Mexout}
           +-               -+  +-               -+
           |  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  |
           +-               -+  +-               -+
  \end{Mexout}
\end{MExample}

%\end{Mhelppage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Inversions of permutations
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\MethodSection{Inversions, Lehmer code and reduced words of permutations}

%\begin{Mhelppage}{permutations::inversions}{F.~Hivert, N~.Thiéry}
%  [ImplState=stable,TestState=stable,DocState=stable]

%\begin{MInfo}
%  \eng{inversions, Lehmer code and reduced words of permutations}
%\end{MInfo}

%\begin{MIntro}
%  \eng{Functions related to inversions of permutations, Lehmer code and
%    reduced words of permutations.}
%\end{MIntro}

\begin{MDetails}
  \eng{An \emph{inversion} of a permutation $p:=(p_1,p_2,\dots,p_n)$ is a
    pair of positions $\{i,j\}$ such that $i<j$ and $p_i>p_j$. It is
    represented in \mupad\ as a set of two positive integers
    \Mex{\{i,j\}}.}
  
  \eng{The \emph{sign} of a permutation $p$ is $-1$ if $p$ has an odd
    number of inversions, and $1$ otherwise.}
  
  \eng{The \emph{Lehmer code} of a permutation is the list
    $(c_1,c_2,\dots,c_n)$ such that $c_i=|\{j>i, p_i<p_j\}$.  Note
    that $c_i\leq n-i$. The \emph{cocode} is the list
    $(c_1,c_2,\dots,c_n)$ such that $c_i=|\{j<i, p_j>p_i\}$.}
  
  \eng{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 $n$ and words
    $(c_1,\dots,c_n)$ such that $c_i\leq n-i$ (resp $c_i<i$). If $w$
    is a non standard permutation, then decoding the Lehmer code of
    $w$ yields the standardized of $w$.}
  
  \eng{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.}
  
  \eng{The functions described here only work for permutations whose
    elements can be ordered by \Mup{<}.}
  
  \eng{Let $s_i$ denote the elementary transposition $(i, i+1)$. A \emph{word
    for the permutation $\sigma$} is a list $(i_1, \dots, i_l)$ such that
    $\sigma$ is equal to the product $s_{i_1}s_{i_2}\dots s_{i_l}$. A word is
    said to be \emph{reduced} if it is of minimal length among all the words
    for the same permutation. The length of a reduced word for $\sigma$ is
    equal to the number of inversions of $\sigma$. In \mupad\ words are
    represented by lists of positive integers.} 
\end{MDetails}

\begin{MMethodDetails}{inversions}
  \infoEng{list of the inversions of a permutation}
  \call{\Mtype{permutation} p}%
  \eng{Returns the list of the inversions of the permutation
    \Mpar{p}.}
\end{MMethodDetails}

\begin{MMethodDetails}{inversionsNumber}
  \infoEng{number of inversions of a permutation}
  \call{\Mtype{permutation} p}
  \eng{Returns the number of inversions of the permutation \Mpar{p}.}
\end{MMethodDetails}

\begin{MMethodDetails}{sign}
  \infoEng{sign of a permutation}
  \call{\Mtype{permutation} p}
  \eng{Returns the sign of the permutation \Mpar{p}.}
\end{MMethodDetails}

\begin{MMethodDetails}{isEven}
  \infoEng{parity of a permutation}
  \call{\Mtype{permutation} p}
  \eng{Tests if the permutation \Mpar{p} is even.}
\end{MMethodDetails}

\begin{MMethodDetails}{code}
  \infoEng{Lehmer code of a permutation}
  \call{\Mtype{permutation} p}
  \eng{Returns the Lehmer code of the permutation \Mpar{p}.}
\end{MMethodDetails}

\begin{MMethodDetails}{fromCode}
  \infoEng{standard permutation from its code}
  \call{\Mtype{Lehmer code} c\Mopt{, \Mtype{non-negative integer} n}}%
  \eng{Recovers the standard permutation of minimal size from the sequence
    \Mpar{c}, appending the minimum necessary number of zeroes to it so that
    it becomes a Lehmer code.}
  \eng{The argument \Mpar{n}, when provided, specifies the size of the
    returned permutation.}
%  \eng{\Mpar{c} should be a list of integers such that
%    \Mex{c[i]<=nops(c)-i}, for all \Mex{i}.}
\end{MMethodDetails}

\begin{MMethodDetails}{coCode}
  \infoEng{Lehmer cocode of a permutation}
  \call{\Mtype{permutation} p}
  \eng{Returns the Lehmer cocode of the permutation \Mpar{p}.}
\end{MMethodDetails}


\begin{MMethodDetails}{reducedWord}
  \infoEng{Reduced word of a standard permutation}
  \call{\Mtype{permutation} p}
  \eng{Returns a reduced word of the permutation \Mpar{p}.}
\end{MMethodDetails}
  
\begin{MMethodDetails}{reducedWords}
  \infoEng{List of reduced words of a standard permutation}
  \call{\Mtype{permutation} p}
  \eng{Returns the list of all reduced words of the permutation \Mpar{p}.}
\end{MMethodDetails}
  
\begin{MMethodDetails}{fromReducedWord}
  \infoEng{Standard permutation from a (reduced) word}
  \call{\Mtype{reduced word} w \Mopt{, \Mtype{non-negative integer} n}}
  \eng{Returns the standard permutation of minimal size that is the product of
    the elementary transpositions represented by \Mpar{w}. Note that this word
    does not need to be reduced.}
  \eng{The argument \Mpar{n}, when provided, specifies the size of the
    returned permutation.}
\end{MMethodDetails}

\begin{MExample}{ex-inversions}
  \eng{The number of inversions of a permutation, also called its
    \emph{length}, can be computed with:}
  \begin{Mexin}
combinat::permutations::inversionsNumber([1, 2, 6, 4, 7, 3, 5])
  \end{Mexin}
  \begin{Mexout}
                               6
  \end{Mexout}
  \eng{Here is the list of the $6$ inversions of the previous permutation:}
  \begin{Mexin}
combinat::permutations::inversions([1, 2, 6, 4, 7, 3, 5])
  \end{Mexin}
  \begin{Mexout}
       [{3, 4}, {3, 6}, {3, 7}, {4, 6}, {5, 6}, {5, 7}]
  \end{Mexout}
  \eng{Note that this also works for non-standard permutations, as
    long as the elements can be ordered with \Mup{<}:}
  \begin{Mexin}
combinat::permutations::inversionsNumber([1, 3, 2, 1, 2, 1]);
combinat::permutations::inversions([1, 3, 2, 1, 2, 1]);
combinat::permutations::inversions(["c", "b", "a"])
  \end{Mexin}
  \begin{Mexout}
                               7

   [{2, 3}, {2, 4}, {2, 5}, {2, 6}, {3, 4}, {3, 6}, {5, 6}]

                   [{1, 2}, {1, 3}, {2, 3}]
  \end{Mexout}
  \eng{The sign of any transposition is $-1$:}
  \begin{Mexin}
combinat::permutations::sign([4, 2, 3, 1, 5])
  \end{Mexin}
  \begin{Mexout}
                              -1
  \end{Mexout}
  \eng{Furthermore, the sign defines a multiplicative morphism from
    the symmetric group into $\{-1,1\}$. We check this for the
    symmetric group of order $4$:}
  \begin{Mexin}
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)))
  \end{Mexin}
  \begin{Mexout}
                             TRUE
  \end{Mexout}
\end{MExample}
\begin{MExample}{ex-code}
  \eng{The code provides a bijection between permutations of
    \Mex{[$1..n]}%$
    and lists \Mex{c} of length \Mex{n} such that \Mex{c[i]<=n-i}:}
  \begin{Mexin}
for p in combinat::permutations(3) do 
    code := combinat::permutations::code(p); 
    p2   := combinat::permutations::fromCode(code); 
    print(p, code, p2);
end_for
  \end{Mexin}
  \begin{Mexout}
                [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]
  \end{Mexout}
  \eng{If $w$ is a non standard permutation, then decoding the code of
    $w$ yields the standardized of $w$:}
    \begin{Mexin}
w := [2, 3, 1, 2, 2, 4, 5, 1]:
code := combinat::permutations::code(w);
combinat::words::standard(w), combinat::permutations::fromCode(code)
  \end{Mexin}
  \begin{Mexout}
                   [2, 4, 0, 1, 1, 1, 1, 0]

      [3, 6, 1, 4, 5, 7, 8, 2], [3, 6, 1, 4, 5, 7, 8, 2]
  \end{Mexout}
\end{MExample}
\begin{MExample}{ex-reduced}
  \eng{The permutation corresponding to a given product of elementary
       transpositions can be computed with:}
  \begin{Mexin}
combinat::permutations::fromReducedWord([3,2,3,1,2,3,1]);
  \end{Mexin}
  \begin{Mexout}
                         [3, 4, 2, 1]
  \end{Mexout}
  \eng{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 \Mex{[3, 4, 2, 1]}. It is not the case of the
    product we studied before.}
  \begin{Mexin}
map(combinat::permutations::reducedWords([3,4,2,1]),nops);
nops([3,2,3,1,2,3,1]);
  \end{Mexin}
  \begin{Mexout}
                        [5, 5, 5, 5, 5]

                               7
  \end{Mexout}
  \eng{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:}
  \begin{Mexin}
combinat::permutations::reducedWord([3,5,4,6,2,1]);
  \end{Mexin}
  \begin{Mexout}
                [2, 1, 4, 3, 2, 4, 3, 5, 4, 5]
  \end{Mexout}
\end{MExample}
%\end{Mhelppage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Cycle decomposition of standard permutations
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\MethodSection{Cycle decomposition of standard permutations}

%\begin{Mhelppage}{permutations::cycles}{N~.Thiéry, F.~Hivert}
%  [ImplState=stable,TestState=stable,DocState=stable]

%\begin{MInfo}
%  \eng{cycle decomposition of standard permutations}
%\end{MInfo}

%\begin{MIntro}
%  \eng{Functions related to cycle decomposition and fixed points of standard
%    permutations.}
%\end{MIntro}

\begin{MDetails}
  \eng{A \emph{cycle} $p:=(c_1,c_2,\Mseq{},c_k)$ of \emph{length} $k$
    is the permutation such that $p(c_1):=c_2, p(c_2):=c_3, \dots,
    p(c_k):=c_1$, and $p(i):=i$ for $i\not\in \{c_1,\dots,c_k\}$. Such
    a cycle is represented in \mupad\ by a list
    $\Mex{[c1,\Mseq{},ck]}$.  This representation is unique if, for
    example, \Mex{c1} is chosen to be minimal.}
  
  \eng{A cycle of length $1$ is equal to the identity permutation and
    is called \emph{trivial}.}
  
  \eng{Two disjoint cycles commute.}
  
  \eng{Any standard permutation $p$ can be written as a product of
    disjoint cycles. This is called the \emph{cycle decomposition} of
    $p$. It is unique up to the order of the cycles, and up to the first
    element of the cycles.}
\end{MDetails}

%\MDeclareOption{\Duplicate}{Duplicate}

\begin{MMethodDetails}{cycles}
  \infoEng{cycle decomposition of a standard permutation}
  \call{\Mtype{standard permutation} p}%
  \eng{Returns the cycle decomposition of \Mpar{p}. This is the list
    of the non-trivial cycles of \Mpar{p}. Each cycle is represented
    by the list \Mex{[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.}
\end{MMethodDetails}

\begin{MMethodDetails}{cycleType}
  \infoEng{cycle type of a standard permutation}
  \call{\Mtype{standard permutation} p}%
  \eng{Returns the cycle type of the permutation \Mpar{p}, as a
    partition. This is the decreasing list of the lengths of the
    cycles of \Mpar{p}.}
\end{MMethodDetails}

\begin{MMethodDetails}{fromCycles}
  \infoEng{standard permutation from its cycle decomposition}
  \call{\Mtype{list of list of integers} cycleList \Mopt{, \Mtype{integer} n}}%
  \eng{Returns the standard permutation of minimal size that has the given
    cycle list. Note that this minimal size corresponds to the greatest
    element in \Mpar{cycleList}.}
  \eng{Trivial cycles of length \Mex{1} may be omitted if the greatest element
    of the permutation is not in a cycle of length \Mex{1}.}
  \eng{The argument \Mpar{n}, when provided, specifies the size of the
    returned permutation.}
\end{MMethodDetails}

\begin{MMethodDetails}{fixedPoints}
  \infoEng{list of the fixed points of a standard permutation}
  \call{\Mtype{standard permutation} p}%
  \eng{Returns the list of the fixed points of \Mpar{p}.}
\end{MMethodDetails}

\begin{MMethodDetails}{fixedPointsNumber}
  \infoEng{number of fixed points of a standard permutation}
  \call{\Mtype{standard permutation} p}%
  \eng{Returns the number of fixed points of \Mpar{p}.}
\end{MMethodDetails}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Examples on cycles/inversions
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{MExample}{ex-cycles}
  \eng{The cycles of a permutation can be computed with:}
  \begin{Mexin}
combinat::permutations::cycles([3,5,1,2,4]);
  \end{Mexin}
  \begin{Mexout}
                      [[1, 3], [2, 5, 4]]
  \end{Mexout}
  \eng{You can recover the initial permutation by two different ways,
    forgetting or not the cycle of length $1$:}
  \begin{Mexin}
combinat::permutations::fromCycles([[1, 3], [2, 5], [4]]),
combinat::permutations::fromCycles([[1, 3], [2, 5]]);
  \end{Mexin}
  \begin{Mexout}
               [3, 5, 1, 4, 2], [3, 5, 1, 4, 2]
  \end{Mexout}
  \eng{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:}
    
  \begin{Mexin}
select(combinat::permutations::list(4),
  z-> combinat::permutations::cycleType(z)=[2,2]);
nops(%), 4!/(2^2*2!);
  \end{Mexin}
  \begin{Mexout}
          [[2, 1, 4, 3], [3, 4, 1, 2], [4, 3, 2, 1]]

                             3, 3
  \end{Mexout}
\end{MExample}
\begin{MExample}{ex-ptsfixes}
  \eng{To compute the list or the number of fixed points of a permutation, you
    can use:}
  \begin{Mexin}
combinat::permutations::fixedPoints([6, 7, 3, 8, 5, 9, 2, 1, 4]);
combinat::permutations::fixedPointsNumber([6, 7, 3, 8, 5, 9, 2, 1, 4]);
  \end{Mexin}
  \begin{Mexout}
                            [3, 5]

                               2
  \end{Mexout}
  \eng{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:}
  \begin{Mvin}{test=false}
combinat::permutations::fixedPoints(combinat::permutations::random(20)); 
  \end{Mvin}
  \begin{Mvout}{test=false}
                             [13]
  \end{Mvout}
\end{MExample}
%\end{Mhelppage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Help page on Descents
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\MethodSection{Descents, major indice and major code of permutations}

%\begin{Mhelppage}{permutations::descents}{N~.Thiéry,F.~Hivert}
%  [ImplState=stable,TestState=stable,DocState=stable]
%
\MDeclareOption{\FinalDescent}{FinalDescent}
%
%\begin{MInfo}
%  \eng{descents, major indice and major code of permutations}
%\end{MInfo}

%\begin{MIntro}
%  \eng{Functions related to descents, major indice and major code of
%    permutations.}
%\end{MIntro}

\begin{MDetails}
  \eng{A \emph{descent} of a permutation $p=(p_1,p_2,\dots,p_n)$ is an
    integer $i$ such that and $p_i>p_{i+1}$.}
  \eng{Let $des=(d_1,d_2,\ldots,d_k)$ be the increasing list of the
    descents of a permutation $p$. Let
    $I=(d_1,d_2-d_1,d_3-d_2,\ldots,d_k-d_{k-1})$ be its corresponding
    composition. We say that $I$ is the \emph{ribbon shape} of $p$, or,
    equivalently that $p$ has $I$ as ribbon shape.}
\end{MDetails}

\begin{MMethodDetails}{descents}
  \infoEng{list of the descents of a permutation}
%  \call{\Mtype{permutation} p}%
  \call{\Mtype{permutation} p\Mopt{, FinalDescent}}%
  \eng{Returns the list of the \emph{descents} of the permutation
    \Mpar{p}, that is, the list of integers $i$ such that
    \Mex{p[i]>p[i+1]}.}
  \eng{With the option \FinalDescent, the last position of a non empty
    permutation is also considered as a descent.}
\end{MMethodDetails}

\begin{MMethodDetails}{descentsNumber}
  \infoEng{number of descents of a permutation}
%  \call{\Mtype{permutation} p}%
  \call{\Mtype{permutation} p\Mopt{, FinalDescent}}%
  \eng{Returns the number of \emph{descents} of the permutation \Mpar{p}.}
  \eng{With the option \FinalDescent, the last position of a non empty
    permutation is also considered as a descent.}
\end{MMethodDetails}

\begin{MMethodDetails}{majorIndex}
  \infoEng{major index of a permutation}
%  \call{\Mtype{permutation} p}%
  \call{\Mtype{permutation} p\Mopt{, FinalDescent}}%
  \eng{Returns the \emph{major index} of the permutation \Mpar{p},
    that is the sum of the descents of \Mpar{p}.}
  \eng{With the option \FinalDescent, the last position of a non empty
    permutation is also considered as a descent.}
\end{MMethodDetails}

\begin{MMethodDetails}{majorCode}
  \infoEng{major code of a permutation}
  \call{\Mtype{permutation} p}%
  \eng{Returns the \emph{major code} of the permutation \Mpar{p}, that is the
    list \Mex{[maj(p1)..maj(pn)]} of the major indices of the permutations $p_i$,
    obtained by erasing the letters smaller than $i$ in \Mpar{p}.}
\end{MMethodDetails}

\begin{MMethodDetails}{fromMajorCode}
  \infoEng{permutation from its major code}
  \call{\Mtype{major code} c}%
  \eng{Returns the permutations whose \emph{major code} is \Mpar{p}.
  this is the converse bijection of \Mpar{majorCode}}
\end{MMethodDetails}

\begin{MMethodDetails}{descentPolynomial}
  \infoEng{descent polynomial of a permutation}
  \call{\Mtype{permutation} p, \Mtype{variable} z}%
  \eng{Returns the descent polynomial of the permutation \Mpar{p} in
    the variable \Mpar{z}. It is the product of the monomials
    \Mex{z[p[1]]z[p[2]]\Mseq{}z[p[i]]} for all descents \Mex{i} of the
    permutation \Mpar{p}.}
  \eng{Note that the the last position of a non empty
    permutation is never considered as a descent.}
\end{MMethodDetails}

\begin{MMethodDetails}{descentsToMin}
  \infoEng{smallest permutation having a given descent set}
  \call{\Mtype{list or set} s\Mopt{, \Mtype{integer} n}}%
  \eng{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
    \Mpar{s}.}
  \eng{The argument \Mpar{n}, when provided, specifies the size of the
    returned permutation.}
\end{MMethodDetails}

\begin{MMethodDetails}{descentsToMax}
  \infoEng{greatest permutation having a given descent set}
  \call{\Mtype{list or set} s\Mopt{, \Mtype{integer} n}}%
  \eng{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 
    \Mpar{s}.}
  \eng{The argument \Mpar{n}, when provided, specifies the size of the
    returned permutation.}
\end{MMethodDetails}

\begin{MMethodDetails}{descentsCompositionToMin}
  \infoEng{smallest permutation having a given ribbon shape}
  \call{\Mtype{composition} s}%
  \eng{Returns the standard permutation of minimal size and smallest one with
    respect to the number of inversions that has the ribbon shape \Mpar{s}.
    Note that this minimal size corresponds to the sum of the entries of
    \Mpar{s}.}
\end{MMethodDetails}

\begin{MMethodDetails}{descentsCompositionToMax}
  \infoEng{greatest permutation having a given ribbon shape}
  \call{\Mtype{composition} s}%
  \eng{Returns the standard permutation of minimal size and greatest one with
    respect to the number of inversions that has the ribbon shape \Mpar{s}.
    Note that this minimal size corresponds to the sum of the entries of
    \Mpar{s}.}
\end{MMethodDetails}

\begin{MMethodDetails}{fromDescents}
  \infoEng{list of standard permutations with a given descent set}
  \call{\Mtype{list or set} s\Mopt{, \Mtype{integer} n}}%
  \eng{Returns the list of standard permutations of minimal size having
    the descent set \Mpar{s}.
    Note that this minimal size corresponds to the greatest element in 
    \Mpar{s}.}
  \eng{The argument \Mpar{n}, when provided, specifies the size of the
    returned permutation.}
\end{MMethodDetails}

\begin{MMethodDetails}{fromDescentsComposition}
  \infoEng{list of standard permutations having a given ribbon shape}
  \call{\Mtype{composition} s}%
  \eng{Returns the list of standard permutations of minimal size that
    have the ribbon shape \Mpar{s}.
    Note that this minimal size corresponds to the sum of the entries of
    \Mpar{s}.}
\end{MMethodDetails}

% In the long term, in might be preferable to make a separate
% page for young subgroups

\begin{MMethodDetails}{youngSubgroup}[ImplState=beta,TestState=beta,DocState=beta]
  \infoEng{young subgroup}
  \call{\Mtype{composition} c}%
  \eng{Returns the list of the standard permutations in the
    \emph{Young subgroup} (also called parabolic subgroup) $\mathfrak
    S_{c_1} \times\dots\times \mathfrak S_{c_k}$ of the symmetric
    group $S_{c_1+\dots+c_k}$; otherwise said the standard
    permutations which stabilize the consecutive intervals
    $[1,\dots,c_1], [c_1+1,\dots, c_1+c_2], \dots$ whose length are
    given by $c$.}
  
  \eng{Note: \Mex{combinat::permutations::youngSubgroup} is actually a
    combinatorial class, with the usual \Mex{list}, \Mex{count} and
    \Mex{generator} methods.}
\end{MMethodDetails}

\begin{MMethodDetails}{modYoungSubgroup}
  \infoEng{permutation modulo a Young subgroup}
  \call{\Mtype{permutation} p, \Mtype{composition} c}%
  
  \eng{This returns a canonical representative of \Mpar{p} modulo the
    right action of the Young subgroup $\mathfrak{S}_c$ (see above) on
    the positions.}%
  
  \eng{This boils down to sorting $p$ in the consecutive intervals
    whose lengths are given by $c$.}
\end{MMethodDetails}

\begin{MMethodDetails}{fromSetPartition}[ImplState=beta,TestState=beta,DocState=beta]
  \infoEng{permutations stabilizing a standard set partition}
  \call{\Mtype{standard set partition} setPartition}%
  \eng{\Mpar{setPartition} is a set partition of $\{1,\dots,n\}$,
    represented by a list of lists or list of sets.}%
  \eng{Returns the list of the standard permutations of
    $\{1,\dots,n\}$ stabilizing each component of
    \Mex{setPartition}.}%
  \eng{Note: \Mex{combinat::permutations::fromSetPartition} is
    actually a combinatorial class, with the usual \Mex{list},
    \Mex{count} and \Mex{generator} methods.}
\end{MMethodDetails}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Examples on descents
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{MExample}{ex-descents1}
  \eng{The descents of a permutation are computed as:}
  \begin{Mexin}
combinat::permutations::descents([2, 1, 6, 4, 7, 3, 5])
  \end{Mexin}
  \begin{Mexout}
                           [1, 3, 5]
  \end{Mexout}
  \eng{The sum of the descents is called the major index:}
  \begin{Mexin}
combinat::permutations::majorIndex([2, 1, 6, 4, 7, 3, 5])
  \end{Mexin}
  \begin{Mexout}
                               9
  \end{Mexout}
  \eng{It is the total degree of the descent polynomial, that is always a
    monomial on permutations:}
  \begin{Mexin}
combinat::permutations::descentPolynomial([2, 1, 6, 4, 7, 3, 5],z)
  \end{Mexin}
  \begin{Mexout}
                      2     3          2
                  z[1]  z[2]  z[4] z[6]  z[7]
  \end{Mexout}
\end{MExample}


\begin{MExample}{ex-descents1}
  \eng{We compute the major code of a permutation:}
  \begin{Mexin}
combinat::permutations::majorCode([2, 1, 6, 4, 7, 3, 5])
  \end{Mexin}
  \begin{Mexout}
                     [3, 2, 0, 2, 2, 0, 0]
  \end{Mexout}
  \eng{The sum of the major code is the major index:}
  \begin{Mexin}
combinat::permutations::majorIndex([2, 1, 6, 4, 7, 3, 5])
  \end{Mexin}
  \begin{Mexout}
                               9
  \end{Mexout}
  \eng{One can retrieve a permutations knowing its major code:}
  \begin{Mexin}
combinat::permutations::fromMajorCode([3, 2, 0, 2, 2, 0, 0])
  \end{Mexin}
  \begin{Mexout}
                     [2, 1, 6, 4, 7, 3, 5]
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-descentsTo}
  \eng{To compute the smallest element of a descent class, you can use:}
  \begin{Mexin}
combinat::permutations::descentsToMin([2, 1, 5, 9], 12)
  \end{Mexin}
  \begin{Mexout}
            [3, 2, 1, 4, 6, 5, 7, 8, 10, 9, 11, 12]
  \end{Mexout}
  \eng{To get the same result using ribbon shapes, one can write:}
  \begin{Mexin}
combinat::permutations::descentsCompositionToMin([1, 1, 3, 4, 3])
  \end{Mexin}
  \begin{Mexout}
            [3, 2, 1, 4, 6, 5, 7, 8, 10, 9, 11, 12]
  \end{Mexout}
  \eng{To compute the greatest element of a descent class, you can use:}
  \begin{Mexin}
combinat::permutations::descentsToMax([2, 1, 5, 9], 12)
  \end{Mexin}
  \begin{Mexout}
            [12, 11, 8, 9, 10, 4, 5, 6, 7, 1, 2, 3]
  \end{Mexout}
  \eng{To get the same result using ribbon shapes, one can write:}
  \begin{Mexin}
combinat::permutations::descentsCompositionToMax([1, 1, 3, 4, 3])
  \end{Mexin}
  \begin{Mexout}
            [12, 11, 8, 9, 10, 4, 5, 6, 7, 1, 2, 3]
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-fromdescents}
  \eng{To compute the list of permutations that have a given descent set,
    you can use:}
 \begin{Mexin}
combinat::permutations::fromDescents([3, 5, 1])
  \end{Mexin}
  \begin{Mexout}
[[2, 1, 4, 3, 5], [2, 1, 5, 3, 4], [3, 1, 4, 2, 5],

   [3, 1, 5, 2, 4], [3, 2, 4, 1, 5], [3, 2, 5, 1, 4],

   [4, 1, 3, 2, 5], [4, 1, 5, 2, 3], [4, 2, 3, 1, 5],

   [4, 2, 5, 1, 3], [4, 3, 5, 1, 2], [5, 1, 3, 2, 4],

   [5, 1, 4, 2, 3], [5, 2, 3, 1, 4], [5, 2, 4, 1, 3],

   [5, 3, 4, 1, 2]]
  \end{Mexout}
  \eng{To get the same result using ribbon shapes, one can write:}
  \begin{Mexin}
combinat::permutations::fromDescentsComposition([1, 2, 2])
  \end{Mexin}
  \begin{Mexout}
[[2, 1, 4, 3, 5], [2, 1, 5, 3, 4], [3, 1, 4, 2, 5],

   [3, 1, 5, 2, 4], [3, 2, 4, 1, 5], [3, 2, 5, 1, 4],

   [4, 1, 3, 2, 5], [4, 1, 5, 2, 3], [4, 2, 3, 1, 5],

   [4, 2, 5, 1, 3], [4, 3, 5, 1, 2], [5, 1, 3, 2, 4],

   [5, 1, 4, 2, 3], [5, 2, 3, 1, 4], [5, 2, 4, 1, 3],

   [5, 3, 4, 1, 2]]
  \end{Mexout}
  \eng{Here are all the permutations in the Young subgroup
    $\mathfrak{S}_{3,2}$:}
  \begin{Mexin}
combinat::permutations::youngSubgroup([2, 3])
  \end{Mexin}
  \begin{Mexout}
[[1, 2, 3, 4, 5], [1, 2, 3, 5, 4], [1, 2, 4, 3, 5],

   [1, 2, 4, 5, 3], [1, 2, 5, 3, 4], [1, 2, 5, 4, 3],

   [2, 1, 3, 4, 5], [2, 1, 3, 5, 4], [2, 1, 4, 3, 5],

   [2, 1, 4, 5, 3], [2, 1, 5, 3, 4], [2, 1, 5, 4, 3]]
  \end{Mexout}
  \eng{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:}
  \begin{Mexin}
combinat::permutations::modYoungSubgroup([c, b, e, a, d], [2, 3])
  \end{Mexin}
  \begin{Mexout}
                        [b, c, a, d, e]
  \end{Mexout}
\end{MExample}
%\end{Mhelppage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Help page on peaks
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\MethodSection{Peaks of permutations}

%\begin{Mhelppage}{permutations::peaks}{N~.Thiéry,F.~Hivert}
%  [ImplState=stable,TestState=stable,DocState=stable]
%\begin{MInfo}
%  \eng{Peaks of permutations}
%\end{MInfo}
    
%\begin{MIntro}
%  \eng{Functions related to the peaks of permutations}
%\end{MIntro}
  

\begin{MDetails}
  \eng{A \emph{peak} of a permutation $p=(p_1,p_2,\dots,p_n)$ is an
    integer $i$ such that $p_{i-1}\leq p_i$ and $p_i>p_{i+1}$.}
\end{MDetails}

\begin{MMethodDetails}{peaks}
  \infoEng{list of the peaks of a permutation} 
  \call{\Mtype{permutation} p}% 
  \eng{Returns the list of the \emph{peaks} of the permutation
    \Mpar{p}, that is the list of integers $i$ such that
    \Mex{p[i-1]<=p[i]} and \Mex{p[i]>p[i+1]}.}
\end{MMethodDetails}

\begin{MMethodDetails}{peaksNumber}
  \infoEng{number of peaks of a permutation}
  \call{\Mtype{permutation} p}%
  \eng{Returns the number of \emph{peaks} of the permutation
    \Mpar{p}.} 
\end{MMethodDetails}

\begin{MExample}{ex-peaks}
  \eng{The peaks of a permutation are computed as:}
  \begin{Mexin}
combinat::permutations::peaks([2, 1, 6, 4, 7, 3, 5])
  \end{Mexin}
  \begin{Mexout}
                            [3, 5]
  \end{Mexout}
  \eng{The number of peaks can be directly computed using:}
  \begin{Mexin}
combinat::permutations::peaksNumber([2, 1, 6, 4, 7, 3, 5])
  \end{Mexin}
  \begin{Mexout}
                               2
  \end{Mexout}
\end{MExample}
%\end{Mhelppage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Help page on saillances
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\MethodSection{Saillances of permutations}

%\begin{Mhelppage}{permutations::saillances}{N~.Thiéry,F.~Hivert}
%  [ImplState=stable,TestState=stable,DocState=stable]

%\begin{MInfo}
%  \eng{Saillances of permutations}
%\end{MInfo}

%\begin{MIntro} 
%  \eng{Functions related to the saillances of permutations}
%\end{MIntro}

\begin{MDetails}
  \eng{A \emph{saillance} of a permutation $p=(p_1,p_2,\dots,p_n)$ is
    an integer $i$ such that $p_i>p_j$, for all $j>i$.}
\end{MDetails}

\begin{MMethodDetails}{saillances}
  \infoEng{saillances of a permutation}
  \call{\Mtype{permutation} p}%
  \eng{Returns the saillances of the permutation \Mpar{p}.}
  \eng{This function may be renamed in the future.}
\end{MMethodDetails}

\begin{MMethodDetails}{saillancesNumber}
  \infoEng{saillances number of a permutation}
  \call{\Mtype{permutation} p}%
  \eng{Returns the number of saillances of the permutation \Mpar{p}.}
  \eng{This function may be renamed in the future.}
\end{MMethodDetails}

\begin{MExample}{ex-saillances}
  \eng{The saillances of a permutation are computed as:}
  \begin{Mexin}
combinat::permutations::saillances([7, 1, 4, 6, 2, 5, 3]);
  \end{Mexin}
  \begin{Mexout}
                         [1, 4, 6, 7]
  \end{Mexout}
  \eng{The number of saillances can be directly computed using:}
  \begin{Mexin}
combinat::permutations::saillancesNumber([7, 1, 4, 6, 2, 5, 3]);
  \end{Mexin}
  \begin{Mexout}
                               4
  \end{Mexout}
\end{MExample}
%\end{Mhelppage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Help page on the Bruhat order on permutations
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\MethodSection{Bruhat order on standard permutations}
\Malias{Bruhat}

%\begin{Mhelppage}{permutations::leequalBruhat}{F.~Hivert,N~.Thiéry}
%  [ImplState=stable,TestState=stable,DocState=stable]

%\begin{MInfo}
%  \eng{Bruhat order on standard permutations}
%\end{MInfo}

%\begin{MIntro}
%  \eng{Functions related to the Bruhat order on permutations.}
%\end{MIntro}

\begin{MDetails}
  \eng{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.}

  \eng{A permutation $p1$ is smaller than a permutation $p2$ if and only
    if one of the reduced words of $p1$ is a subsequence (the chosen
    letters do not have to be consecutive) of one of the reduced word of
    $p2$.}

  \eng{The Bruhat order is the transitive closure of the following relation:
    $p1$ is smaller than $p2$ if $p2$ is obtained by multiplying $p1$
    to the left or to the right by a transposition in such a way that it
    increases its number of inversions.}
\end{MDetails}

\begin{MMethodDetails}{leequalBruhat}
  \infoEng{Test of the order relation of two permutations}
  \call{\Mtype{standard permutations} p1, p2}%
  \eng{Returns the boolean answering the question ''Is \Mpar{p1} smaller than
    \Mpar{p2} in the Bruhat order?''}
\end{MMethodDetails}

\begin{MMethodDetails}{bruhatInversions}
  \infoEng{list of inversions in the Bruhat order}
  \call{\Mtype{standard permutation} p}%
  \eng{Returns the list of inversions of \Mpar{p} such that the application of
this inversion to \Mpar{p} decrements its number of inversions.}

  \eng{Equivalently, it returns the list of pairs $(i,j)$, $i<j$ such that
    $p(i)>p(j)$ and such that there exists no $k$ between $i$ and $j$
    satisfying $p(i)>p(k)>p(j)$.}
\end{MMethodDetails}

\begin{MMethodDetails}{predBruhat}
  \infoEng{list of the precedessors of a permutation}
  \call{\Mtype{standard permutation} p}%
  \eng{Returns the list of permutations strictly smaller than \Mpar{p} in the
    Bruhat order, such that there is no permutation between one of those and
    \Mpar{p}.}
\end{MMethodDetails}

\begin{MMethodDetails}{succBruhat}
  \infoEng{list of the successors of a permutation}
  \call{\Mtype{standard permutation} p}%
  \eng{Returns the list of permutations strictly greater than \Mpar{p} in the
    Bruhat order, such that there is no permutation between \Mpar{p} and
    one of those.}
\end{MMethodDetails}

\begin{MMethodDetails}{smallerBruhat}
  \infoEng{list of the permutations smaller than a permutation}
  \call{\Mtype{standard permutation} p}%
  \eng{Returns the list of permutations smaller than or equal to \Mpar{p} in
    the Bruhat order.}
\end{MMethodDetails}

\begin{MMethodDetails}{greaterBruhat}
  \infoEng{list of the permutations greater than a permutation}
  \call{\Mtype{standard permutation} p}%
  \eng{Returns the list of permutations greater than or equal to \Mpar{p} in 
    the Bruhat order.}
\end{MMethodDetails}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Examples on the Bruhat order
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{MExample}{ex-bruhat}
  \eng{To check whether a permutation is smaller than another thanks to the
    Bruhat order, you can call:}
  \begin{Mexin}
combinat::permutations::leequalBruhat([2,4,3,1],[3,4,2,1]);
  \end{Mexin}
  \begin{Mexout}
                             TRUE
  \end{Mexout}
  \eng{You can ask for the inversions of a given permutation by:}
  \begin{Mexin}
combinat::permutations::bruhatInversions([6, 1, 4, 5, 2, 3])
  \end{Mexin}
  \begin{Mexout}
   [{1, 2}, {1, 3}, {1, 4}, {3, 5}, {3, 6}, {4, 5}, {4, 6}]
  \end{Mexout}
  \eng{Applying those inversions to the previous permutation, you exactly get
    the permutations preceding it as you can check with}
  \begin{Mexin}
combinat::permutations::predBruhat([6, 1, 4, 5, 2, 3])
  \end{Mexin}
  \begin{Mexout}
[[1, 6, 4, 5, 2, 3], [4, 1, 6, 5, 2, 3], [5, 1, 4, 6, 2, 3],

   [6, 1, 2, 5, 4, 3], [6, 1, 3, 5, 2, 4], [6, 1, 4, 2, 5, 3],

   [6, 1, 4, 3, 2, 5]]
  \end{Mexout}
  \eng{Now, you can compute the transitive ideal generated by the predecessor
    relation and get (on the previous example, the answer is one page long)}
  \begin{Mexin}
combinat::permutations::smallerBruhat([4, 1, 2, 3])
  \end{Mexin}
  \begin{Mexout}
[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 4, 2, 3],

   [2, 1, 3, 4], [2, 1, 4, 3], [3, 1, 2, 4], [4, 1, 2, 3]]
  \end{Mexout}
  \eng{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:}
  \begin{Mexin}
combinat::permutations::succBruhat([6, 1, 4, 5, 2, 3]);
combinat::permutations::greaterBruhat([4, 1, 2, 3])
  \end{Mexin}
  \begin{Mexout}
[[6, 4, 1, 5, 2, 3], [6, 2, 4, 5, 1, 3], [6, 1, 5, 4, 2, 3],

   [6, 1, 4, 5, 3, 2]]

[[4, 3, 2, 1], [4, 3, 1, 2], [4, 2, 3, 1], [4, 2, 1, 3],

   [4, 1, 3, 2], [4, 1, 2, 3]]
  \end{Mexout}
\end{MExample}
%\end{Mhelppage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Help page on the Permutohedron order on permutations
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\MethodSection{Permutohedron order on standard permutations}
\Malias{Permutohedron}

%\begin{Mhelppage}{permutations::leequalPermutohedron}{F.~Hivert,N~.Thiéry}
%  [ImplState=stable,TestState=stable,DocState=stable]


\MDeclareOption{\Right}{Right}
\MDeclareOption{\Left}{Left}

%\begin{MInfo}
%  \eng{permutohedron order on standard permutations}
%\end{MInfo}

%\begin{MIntro}
%  \eng{Functions related to the permutohedron order on permutations.}
%\end{MIntro}

\begin{MDetails}
  \eng{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''.}

  \eng{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.}

  \eng{A permutation $p1$ is smaller than a permutation $p2$ in the left
    (resp. right) permutohedron if and only if any reduced word of $p1$ is a
    suffix (resp. prefix) of one of the reduced word of $p2$.}

  \eng{Equivalently, $p1$ is smaller than $p2$ in the left
    (resp. right) permutohedron if and only if one can go from $p1$ to $p2$
    by multiplying $p1$ on the left (resp. right) by a sequence of elementary
    transpositions that increment at each step its number of inversions.}

%\eng{Each permutohedron has a lattice structure...}
\end{MDetails}

\begin{MMethodDetails}{leequalPermutohedron}
\infoEng{Test of the order relation of two permutations}
  \call{\Mtype{standard permutations} p1, p2\Mopt{, Left}}%
  \eng{Returns the boolean answering the question ''Is \Mpar{p1} smaller than
    \Mpar{p2} in the permutohedron order?''} 

  \eng{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.}
\end{MMethodDetails}

\begin{MMethodDetails}{predPermutohedron}
  \infoEng{list of the precedessors of a permutation}
  \call{\Mtype{standard permutation} p\Mopt{, Left}}%
  \eng{Returns the list of permutations strictly smaller than \Mpar{p} in the
    permutohedron order, such that there is no permutation between one of those
    and \Mpar{p}.}

  \eng{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.}
\end{MMethodDetails}

\begin{MMethodDetails}{succPermutohedron}
  \infoEng{list of the successors of a permutation}
  \call{\Mtype{standard permutation} p\Mopt{, Left}}%
  \eng{Returns the list of permutations strictly greater than \Mpar{p} in the
    permutohedron order, such that there is no permutation between \Mpar{p} and
    one of those.}

  \eng{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.}
\end{MMethodDetails}

\begin{MMethodDetails}{smallerPermutohedron}
  \infoEng{list of the permutations smaller than a permutation}
  \call{\Mtype{standard permutation} p\Mopt{, Left}}%
  \eng{Returns the list of permutations smaller than or equal to \Mpar{p} in
    the permutohedron order.}

  \eng{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.}
\end{MMethodDetails}

\begin{MMethodDetails}{greaterPermutohedron}
  \infoEng{list of the permutations greater than a permutation}
  \call{\Mtype{standard permutation} p\Mopt{, Left}}%
  \eng{Returns the list of permutations greater than or equal to \Mpar{p} in
    the permutohedron order.}

  \eng{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.}
\end{MMethodDetails}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Examples on the permutohedron order
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{MExample}{ex-permutohedron-right}
  \eng{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:}
  \begin{Mexin}
combinat::permutations::leequalPermutohedron([3,2,1,4],[4,2,1,3]);
  \end{Mexin}
  \begin{Mexout}
                             FALSE
  \end{Mexout}
  \eng{To compute what permutations precede a given permutation, you can use:}
  \begin{Mexin}
combinat::permutations::predPermutohedron([4, 2, 1, 3]);
  \end{Mexin}
  \begin{Mexout}
                 [[2, 4, 1, 3], [4, 1, 2, 3]]
  \end{Mexout}
  \eng{Now, you can compute the transitive ideal generated by the predecessor
    relation and get:}
  \begin{Mexin}
combinat::permutations::smallerPermutohedron([4, 2, 1, 3]);
  \end{Mexin}
  \begin{Mexout}
[[1, 2, 3, 4], [1, 2, 4, 3], [2, 1, 3, 4], [2, 1, 4, 3],

   [2, 4, 1, 3], [1, 4, 2, 3], [4, 1, 2, 3], [4, 2, 1, 3]]
  \end{Mexout}
  \eng{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:}
  \begin{Mexin}
combinat::permutations::succPermutohedron([4, 2, 1, 3]);
combinat::permutations::greaterPermutohedron([4, 2, 1, 3]);
  \end{Mexin}
  \begin{Mexout}
                        [[4, 2, 3, 1]]

          [[4, 3, 2, 1], [4, 2, 3, 1], [4, 2, 1, 3]]
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-permutohedron-left}
  \eng{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:}
  \begin{Mexin}
combinat::permutations::leequalPermutohedron([3,2,1,4],[4,2,1,3],Left);
  \end{Mexin}
  \begin{Mexout}
                             TRUE
  \end{Mexout}
  \eng{To compute what permutations precede a given permutation in the Left
    permutohedron, you can use:}
  \begin{Mexin}
combinat::permutations::predPermutohedron([4, 2, 1, 3], Left);
  \end{Mexin}
  \begin{Mexout}
                 [[4, 1, 2, 3], [3, 2, 1, 4]]
  \end{Mexout}
  \eng{Now, you can compute the transitive ideal generated by the predecessor
    relation in the Left permutohedron and get:}
  \begin{Mexin}
combinat::permutations::smallerPermutohedron([4, 2, 1, 3], Left);
  \end{Mexin}
  \begin{Mexout}
[[1, 2, 3, 4], [2, 1, 3, 4], [3, 1, 2, 4], [4, 1, 2, 3],

   [1, 3, 2, 4], [2, 3, 1, 4], [3, 2, 1, 4], [4, 2, 1, 3]]
  \end{Mexout}
  \eng{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:}
  \begin{Mexin}
combinat::permutations::succPermutohedron([4, 2, 1, 3], Left);
combinat::permutations::greaterPermutohedron([4, 2, 1, 3], Left);
  \end{Mexin}
  \begin{Mexout}
                        [[4, 3, 1, 2]]

          [[4, 3, 2, 1], [4, 3, 1, 2], [4, 2, 1, 3]]
  \end{Mexout}
\end{MExample}
%\end{Mhelppage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Help page on patterns
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\MethodSection{Patterns of standard permutations}

%\begin{Mhelppage}{permutations::hasPattern}{F.~Hivert,N~.Thiéry}
%  [ImplState=stable,TestState=stable,DocState=stable]
%\begin{MInfo}
%  \eng{Patterns on standard permutations}
%\end{MInfo}

%\begin{MIntro}
%  \eng{Functions related to patterns of standard permutations}
%\end{MIntro}

\begin{MDetails}
  \eng{A permutation $perm=(p_1,p_2,\ldots,p_n)$ of size $n$ \emph{avoids the
    pattern} $pattt=(s_1,s_2,\ldots,s_k)$ of size $k$ if and only if there is
    no subsequence $i_{\pi(1)} < i_{\pi(2)} < \ldots < i_{\pi(k)}$ in $[1,n]$
    such that $\sigma(i_1) < \sigma(i_2) < \ldots < \sigma(i_k)$.}
\end{MDetails}

\begin{MMethodDetails}{hasPattern}
\infoEng{Test of existence of a pattern in a standard permutation}
  \call{\Mtype{standard permutations} perm, patt}%
  \eng{Returns the boolean answering the question ''Is \Mpar{patt} a pattern
    appearing in \Mpar{perm}?''}
\end{MMethodDetails}

\begin{MMethodDetails}{patternPositions}
  \infoEng{list of the positions of a pattern in a permutation}
  \call{\Mtype{standard permutations} perm, patt}%
  \eng{Returns the list of positions where the pattern \Mpar{patt} appears
    in the standard permutations \Mpar{perm}.}
\end{MMethodDetails}

\begin{MExample}{ex-patterns}
  \eng{To check whether a permutation contains a given pattern, you can
    use:}
  \begin{Mexin}
combinat::permutations::hasPattern([3, 5, 1, 4, 6, 2], [1, 3, 2])
  \end{Mexin}
  \begin{Mexout}
                             TRUE
  \end{Mexout}
  \eng{To look at the positions where the pattern appears, you can ask:}
  \begin{Mexin}
combinat::permutations::patternPositions([3, 5, 1, 4, 6, 2], [1, 3, 2])
  \end{Mexin}
  \begin{Mexout}
               [[1, 2, 4], [3, 4, 6], [3, 5, 6]]
  \end{Mexout}
\end{MExample}

\MSuperDomain{combinat::words}

\begin{MAxioms}
  \Mup{Ax::systemRep}
\end{MAxioms}

\end{Mhelppage}
