% $Id: compositions.tex,v 1.1.1.6 2004/10/04 17:25:16 nthiery Exp $
\begin{Mhelppage}{compositions}{F.~Hivert and N.~Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
\Mproofread{nthiery}{10/2003}{proofread}

\begin{MInfo}
  \eng{compositions of an integer}
\end{MInfo}

\MDeclareOption{\MinLength}{MinLength}
\MDeclareOption{\MaxLength}{MaxLength}
\MDeclareOption{\Length}{Length}
\MDeclareOption{\MinPart}{MinPart}
\MDeclareOption{\MaxPart}{MaxPart}
\MDeclareOption{\Inner}{Inner}
\MDeclareOption{\Outer}{Outer}
\MDeclareOption{\MinSlope}{MinSlope}
\MDeclareOption{\MaxSlope}{MaxSlope}

\begin{MIntro}
  \eng{The library \Mthis{} provides functions for counting,
    generating, and manipulating compositions.}
\end{MIntro}

\MKeywords{combinatorics,composition}

\begin{MDetails}
  \eng{A \emph{composition} \Mex{c} of a nonnegative integer \Mpar{n}
    is a list of positive integers with total sum \Mpar{n}.}
  
  \eng{All functions for counting and generating accept the following
    optional constraints on the compositions: \MinLength, \MaxLength,
    \Length, \MinPart, \MaxPart, \Inner, \Outer, \MinSlope, and
    \MaxSlope.  Cf.\ examples~\ref{ex-constraints-length},
    \ref{ex-constraints-parts}, \ref{ex-constraints-containment},
    \ref{ex-constraints-slope}, and \ref{ex-constraints-advanced}.}

  \eng{Generally, compositions of $n$ are used to encode subset of
    $\{1,\dots, n-1\}$ through the bijection:
    \begin{equation}
      I=(i_1, i_2, \dots, i_k) \longmapsto
      \operatorname{Des}(I)= \{i_1, i_1+i_2, \dots,
      i_1+i_2+\dots+i_k\}
    \end{equation}
    The set $\operatorname{Des}(I)$ is called the descents set of the
    composition $I$. The converse bijection is given by
    \begin{equation}
      \{c_1 < c_2 < \dots < c_l\} \subset \{1, \dots, n-1\}
      \longmapsto (c_1, c_2-c_1, \dots, c_l-c_{l-1}, n-c_l)
    \end{equation}
    In \mupad\ the descents set can be stored as a set or a list.}

  \eng{The inclusion of descents set gives rise to a partial order on
    compositions:
    \begin{equation}
    I \leq J \quad\text{if and only if}\quad
    \operatorname{Des}(I) \subset \operatorname{Des}(J)\,.
    \end{equation}
    This order is called the refinement order; the composition $J$ is said to
    be finer than $I$. And $I$ is said to be fatter than $J$.}
\end{MDetails}

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

\MRelatedDomains{combinat::partitions, combinat::words}

\begin{MDomEntries}
  \MDomEntry{domtype}
  \eng{The \mupad\ domain of compositions: \Mup{DOM_LIST}}
\end{MDomEntries}

\begin{MMethodDetails}{isA}
  \infoEng{test if an object is a composition}
  \call{\Mtype{any type} co\Mopt{, \Mtype{nonnegative integer} n\Mopt{, constraints}}}
  \eng{Returns whether \Mpar{co} is a composition.}
  \eng{If the optional argument \Mpar{n} is present, returns whether \Mpar{co} is a
   composition of \Mpar{n}.}
  \eng{If constraints are given, returns whether \Mpar{co} is a composition
       satisfying \Mpar{constraints}.}
\end{MMethodDetails}

\begin{MMethodDetails}{count}
  \infoEng{number of compositions}
  \call{\Mtype{nonnegative integer} n \Mopt{, constraints}}
  \eng{Returns the number of compositions of \Mpar{n} satisfying
    \Mpar{constraints}.}
\end{MMethodDetails}

\begin{MMethodDetails}{generator}
  \infoEng{generator for compositions}
  \call{\Mtype{nonnegative integer} n \Mopt{, constraints}}
  \eng{Returns a generator for the compositions of \Mpar{n} satisfying
    \Mpar{constraints}.}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of the compositions}
  \call{\Mtype{nonnegative integer} n \Mopt{, constraints}}
  \eng{Returns the list of the compositions of \Mpar{n} satisfying
    \Mpar{constraints}.}
\end{MMethodDetails}

\begin{MMethodDetails}{first}
  \infoEng{first composition}
  \call{\Mtype{nonnegative integer} n \Mopt{, constraints}}
  \eng{Returns the first composition of \Mpar{n} satisfying
    \Mpar{constraints} or \Mex{FAIL} if there is none.}
\end{MMethodDetails}
    
\begin{MMethodDetails}{Next}
  \infoEng{next composition}
  \call{\Mtype{composition} c \Mopt{, constraints}}
  \eng{Returns the composition following \Mpar{c} satisfying
    \Mpar{constraints} or \Mex{FAIL} if there is none.}
\end{MMethodDetails}

\begin{MMethodDetails}{descents}
  \infoEng{descents of a composition}
  \call{\Mtype{composition} c}
  \eng{Returns the list of descents of the composition \Mpar{c}}
\end{MMethodDetails}

\begin{MMethodDetails}{descentsSet}
  \infoEng{descents of a composition}
  \call{\Mtype{composition} c}
  \eng{Returns the set of descents of the composition \Mpar{c}}
\end{MMethodDetails}

\begin{MMethodDetails}{fromDescents}
  \infoEng{composition of given descents}
  \call{\Mtype{descent set} s}
  \call{\Mtype{descent list} l}
  \eng{Returns the composition \Mpar{c} whose descents set is \Mpar{s}
    or \Mpar{l}}
\end{MMethodDetails}

\begin{MMethodDetails}{majorIndex}
  \infoEng{major index of a composition}
  \call{\Mtype{composition} c}
  \eng{Returns the major index composition \Mpar{c}, defined as the sum of the
  descents.}
\end{MMethodDetails}

\begin{MMethodDetails}{isFiner}
  \infoEng{compare two compositions for the refinement order}
  \call{\Mtype{composition} c1, \Mtype{composition} c2}
  \eng{Returns whether the composition \Mpar{c1} is finer than the composition
  \Mpar{c2}.}
\end{MMethodDetails}

\begin{MMethodDetails}{finer}
  \infoEng{compositions finer than a composition}
  \call{\Mtype{composition} c}
  \eng{\begin{sloppypar}
    Returns the compositions finer than \Mpar{c}. Note that
    \Mex{compositons::finer} is a full \emph{combinatorial class} that
    implement the standard methods \Mex{compositions::finer::count} and
    \Mex{compositions::finer::generators}.
    \end{sloppypar}}
\end{MMethodDetails}

\begin{MMethodDetails}{fatter}
  \infoEng{compositions fatter than a composition}
  \call{\Mtype{composition} c}%
  \eng{\begin{sloppypar}
    Returns the compositions fatter than \Mpar{c}. Note
    that \Mex{compositons::fatter} is a \emph{combinatorial class} that
    implement the standard methods \Mex{compositions::fatter::count} and
    \Mex{compositions::fatter::generators}.
       \end{sloppypar}}
\end{MMethodDetails}

%%% TODO : finerVectors		  
%%% conjugate
%%% peaks peakComposition fromPeaks
%%% toSkewPartitions)

\begin{MExample}{cp-isA}
\eng{This example shows how to test if an object is of type 
     \Mex{combinat::compositions}:}
\begin{Mexin}
combinat::compositions::isA([3,4]);
combinat::compositions::isA([3,4],7);
combinat::compositions::isA([3,4],5);
\end{Mexin}
\begin{Mexout}
                             TRUE
 
                             TRUE
 
                             FALSE
\end{Mexout}

\eng{The \Mex{combinat::compositions::isA} function admets 
     the same constraints than other functions in the package.}
\begin{Mexin}
combinat::compositions::isA([4,2], 6, Inner=[2, 2], MinPart=2);
combinat::compositions::isA([4,2], 6, Inner=[2, 2], MaxPart=4);
\end{Mexin}
\begin{Mexout}
                             TRUE
 
                             TRUE
\end{Mexout}
\eng{\Mwarn{Please note that given constraints should be compatible:}}
\begin{Mexin}
combinat::compositions::isA([4,1], 5, Inner=[2, 1], MinPart=2); 
\end{Mexin}
\begin{Mexout}
                             TRUE
\end{Mexout}
\eng{See further examples for other constraints.}
\end{MExample}

\begin{MExample}{cp-basic}
\eng{There are $8$ compositions of $4$:}
\begin{Mexin}
combinat::compositions::count(4)
\end{Mexin}
\begin{Mexout}
                               8
\end{Mexout}

\eng{Here is the list:}
\begin{Mexin}
combinat::compositions::list(4)
\end{Mexin}
\begin{Mexout}
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 3], [1, 2, 1], [1, 1, 2],

   [1, 1, 1, 1]]
\end{Mexout}

\eng{You can use the function \Mex{combinat::compositions::first} to get
  the ``first'' composition of a number:}
\begin{Mexin}
combinat::compositions::first(4)
\end{Mexin}
\begin{Mexout}
                              [4]
\end{Mexout}

\eng{Using \Mex{combinat::compositions::Next}, you can calculate the
  ``next'' composition.  This function takes as argument the
  composition relative to which you want the next one:}
\begin{Mexin}
combinat::compositions::Next([4])
\end{Mexin}
\begin{Mexout}
                            [3, 1]
\end{Mexout}

\eng{\Mex{combinat::compositions::Next} returns \Mup{FAIL} when the
  input is the last composition:}
\begin{Mexin}
combinat::compositions::Next([1, 1, 1, 1])
\end{Mexin}
\begin{Mexout}
                             FAIL
\end{Mexout}

\eng{When you want to run through the compositions of a number, you can
  generate them one by one to save memory:}
\begin{Mexin}
g := combinat::compositions::generator(3):
g(); g(); g(); g(); g();
\end{Mexin}
\begin{Mexout}
                              [3]

                            [2, 1]

                            [1, 2]

                           [1, 1, 1]

                             FAIL
\end{Mexout}

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

                            [2, 1]

                            [1, 2]

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

\begin{MExample}{ex-constraints-length}
  \eng{The options \Length, \MinLength, and \MaxLength\ can be used to
    set length constraints. This is the list of the compositions of $4$
    of length $2$:}
  \begin{Mexin}
combinat::compositions::list(4, Length=2)
  \end{Mexin}
  \begin{Mexout}
                   [[3, 1], [2, 2], [1, 3]]
  \end{Mexout}

  \eng{This is the list of the compositions of $4$ of length at least
    $2$:}
  \begin{Mexin}
combinat::compositions::list(4, MinLength=2)
  \end{Mexin}
  \begin{Mexout}
[[3, 1], [2, 2], [2, 1, 1], [1, 3], [1, 2, 1], [1, 1, 2],

   [1, 1, 1, 1]]
  \end{Mexout}
  
  \eng{This is the list of the compositions of $4$ of length at most $2$:}
  \begin{Mexin}
combinat::compositions::list(4, MaxLength=2)
  \end{Mexin}
  \begin{Mexout}
                 [[4], [3, 1], [2, 2], [1, 3]]
  \end{Mexout}
  
  \eng{Setting both \MinLength\ and \MaxLength\ to the same value is
    equivalent to setting \Length\ to this value. This is again the
    list of the compositions of $4$ of length $2$:}
  \begin{Mexin}
combinat::compositions::list(4, MinLength=2, MaxLength=2)
  \end{Mexin}
  \begin{Mexout}
                   [[3, 1], [2, 2], [1, 3]]
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-constraints-parts}
  \eng{The options \MinPart\ and \MaxPart\ can be used to set
    constraints on the sizes of all parts. Using \MaxPart, you can
    select compositions having only small entries. This is the list of
    the compositions of $4$ with all parts at most $2$:}
  \begin{Mexin}
combinat::compositions::list(4, MaxPart=2)
  \end{Mexin}
  \begin{Mexout}
    [[2, 2], [2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]
  \end{Mexout}
  
  \eng{\MinPart\ is complementary to \MaxPart\ and selects compositions
    having only large parts (it takes a non-negative value). This is
    the list of the compositions of $4$ with all parts at least $2$:}
  \begin{Mexin}
combinat::compositions::list(4, MinPart=2)
  \end{Mexin}
  \begin{Mexout}
                         [[4], [2, 2]]
  \end{Mexout}
  
  \eng{By default, the parts of a composition have to be positive. This
    can be changed using the option \MinPart. In the following
    example, the options \Length\ and \MinPart\ are combined together
    to obtain the list of the compositions of $4$ with $3$ nonnegative
    parts:}
  \begin{Mexin}
combinat::compositions::list(4, Length=3, MinPart=0)
  \end{Mexin}
  \begin{Mexout}
[[4, 0, 0], [3, 1, 0], [3, 0, 1], [2, 2, 0], [2, 1, 1],

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

   [0, 4, 0], [0, 3, 1], [0, 2, 2], [0, 1, 3], [0, 0, 4]]
  \end{Mexout}
  
  \eng{If the list you ask for is infinite, the program will not finish,
    as it is be the case for \Mex{combinat::compositions::list(4,
    MinPart=0);}}
  \eng{\Mwarn{Two compositions are considered equivalent whenever they
      differ only by trailing zeroes. Whenever two equivalent
      compositions satisfy the constraints, only the shortest one is
      considered. Hence, this is the list of compositions of $4$ with
      $2$ or $3$ nonnegative parts:}}
  \begin{Mexin}
combinat::compositions::list(4, MinLength=2, MaxLength=3, MinPart=0)
  \end{Mexin}
  \begin{Mexout}
[[4, 0], [3, 1], [3, 0, 1], [2, 2], [2, 1, 1], [2, 0, 2],

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

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

\begin{MExample}{ex-constraints-containment}
%  \eng{Options \Inner\ and \Outer.}%
  \eng{The options \Inner, and \Outer\ can be used to set part-by-part
    containment constraints. This is the list of the compositions of $4$
    bounded above by \Mex{[3, 1, 2]}:}
  \begin{Mexin}
combinat::compositions::list(4, Outer=[3, 1, 2])
  \end{Mexin}
  \begin{Mexout}
                [[3, 1], [2, 1, 1], [1, 1, 2]]
  \end{Mexout}
  \eng{\Outer\ sets \MaxLength\ to the length of its argument.
    Moreover, the parts of \Outer\ may be infinite to clear the
    constraint on specific parts. This is the list of compositions
    of $4$ of length at most $3$ such that the first and third
    parts are at most $1$:}
  \begin{Mexin}
combinat::compositions::list(4, Outer=[1, infinity, 1])
  \end{Mexin}
  \begin{Mexout}
                      [[1, 3], [1, 2, 1]]
  \end{Mexout}
  
  \eng{This is the list of compositions of $4$ bounded below by
    \Mex{[1, 1, 1]}:}
  \begin{Mexin}
combinat::compositions::list(4, Inner=[1, 1, 1])
  \end{Mexin}
  \begin{Mexout}
        [[2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-constraints-slope}
  \eng{The options \MinSlope\ and \MaxSlope\ can be used to set
    constraints on the slope, that is on the difference
    \Mex{p[i+1]-p[i]} of two consecutive parts. This is the list of
    the increasing compositions of $4$:}
  \begin{Mexin}
combinat::compositions::list(4, MinSlope=0)
  \end{Mexin}
  \begin{Mexout}
        [[4], [2, 2], [1, 3], [1, 1, 2], [1, 1, 1, 1]]
  \end{Mexout}
  
  \eng{This is the list of compositions of $4$ such that two
    consecutive parts differ by at most one unit:}
  \begin{Mexin}
combinat::compositions::list(4, MinSlope=-1, MaxSlope=1)
  \end{Mexin}
  \begin{Mexout}
 [[4], [2, 2], [2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-constraints-advanced}
  \eng{The constraints can be combined together in all reasonable
    ways. This is the list of compositions of $5$ of length between
    $2$ and $4$ such that the difference between two consecutive parts
    is between $-2$ and $1$:}
  \begin{Mexin}
combinat::compositions::list(5,
                             MaxSlope=1, MinSlope=-2,
                             MinLength=2, MaxLength=4)
  \end{Mexin}
  \begin{Mexout}
[[3, 2], [3, 1, 1], [2, 3], [2, 2, 1], [2, 1, 2],

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

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

  \eng{Idem with an \Outer\ constraint:}
  \begin{Mexin}
combinat::compositions::list(5,
                             MaxSlope=1, MinSlope=-2,
                             MinLength=2, MaxLength=4,
                             Outer=[2,5,2])
  \end{Mexin}
  \begin{Mexout}
           [[2, 3], [2, 2, 1], [2, 1, 2], [1, 2, 2]]
  \end{Mexout}
  \eng{However, providing incoherent constraints may yield strange
    results. It is up to the user to ensure that the \Inner\ and
    \Outer\ compositions themselves satisfy the parts and slope
    constraints:}
  \begin{Mexin}
combinat::compositions::list(5, Inner=[2, 1], MinPart=2)  
  \end{Mexin}
  \begin{Mexout}
              [[4, 1], [3, 2], [2, 3], [2, 1, 2]]
  \end{Mexout}
\end{MExample}

\begin{MExample}{cp-finer}
  \eng{One can check that those two compositions are not comparable for the
    refinement order:}
  \begin{Mexin}
combinat::compositions::isFiner([4,1,2],[3,1,3]);
combinat::compositions::isFiner([3,1,3],[4,1,2]);
  \end{Mexin}
  \begin{Mexout}
                             FALSE

                             FALSE
  \end{Mexout}
  \eng{To get the list of compositions finer than \Mpar{[4,1,2]}, 
    you can use:}
  \begin{Mexin}
combinat::compositions::finer([4,1,2]);
  \end{Mexin}
  \begin{Mexout}
[[4, 1, 2], [4, 1, 1, 1], [3, 1, 1, 2], [3, 1, 1, 1, 1],

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

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

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

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

   [1, 1, 1, 1, 1, 1, 1]]
  \end{Mexout}
  \eng{To get the list of compositions fatter than
    \Mpar{[4,1,2]}, you can use:}
  \begin{Mexin}
combinat::compositions::fatter([4,1,2]);
  \end{Mexin}
  \begin{Mexout}
               [[7], [5, 2], [4, 3], [4, 1, 2]]
  \end{Mexout}
  \eng{If you only want their number, you can ask:}
  \begin{Mexin}
combinat::compositions::fatter::count([4,1,2]);
  \end{Mexin}
  \begin{Mexout}
                               4
  \end{Mexout}
\end{MExample}

\begin{MBackground}
  \eng{Compositions are naturally ordered lexicographically. The
    functions for counting and generating are directly inherited from
    \Mup{Cat::IntegerListsLexClass} with, by default,
    \Mex{MinPart=1}. The complexity of the generation algorithm is
    constant time amortized for each composition generated.}
  
  \eng{\Mwarn{Except for the trivial cases, counting is done by brute
      force generation.}}
\end{MBackground}

\MSuperDomain{Dom::BaseDomain}  

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

\begin{MChanges}
  \version{2.5}%
  \eng[New library]{\Mthis{} is a new library}
\end{MChanges}

\end{Mhelppage}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: main
%%% End: 
