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

\begin{MInfo}
  \eng{integer vectors}
\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 integer vectors.}
\end{MIntro}

\MKeywords{combinatorics,integer vector}

\begin{MDetails}
  \eng{An \emph{integer vector} \Mex{v} of sum \Mpar{n} with \Mpar{k}
    parts is a list of \Mpar{k} nonnegative integers which sum up to
    \Mpar{n}.}

  \eng{All functions for counting and generating accept the following
    optional constraints on the integer vectors: \MinLength,
    \MaxLength, \Length, \MinPart, \MaxPart, \Inner, \Outer,
    \MinSlope, and \MaxSlope.  Cf.\ examples~\ref{ex-constraints-parts},
    \ref{ex-constraints-containment}, \ref{ex-constraints-slope}, and
    \ref{ex-constraints-advanced}.}
\end{MDetails}

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

\MRelatedDomains{combinat::words}

\begin{MDomEntries}
  \MDomEntry{domtype}
  \eng{The \mupad\ domain used to represent integer vectors: \Mup{DOM_LIST}}
\end{MDomEntries}

\begin{MMethodDetails}{count}
  \infoEng{number of integer vectors}%
  \call{\Mtype{nonnegative integer} n, \Mtype{nonnegative integer} k
    \Mopt{, constraints}}%
  \eng{\begin{sloppypar}
    Returns the number of integer vectors of sum \Mpar{n} with
    \Mpar{k} parts satisfying \Mpar{constraints}.
\end{sloppypar}}
\end{MMethodDetails}

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

\begin{MMethodDetails}{list}
  \infoEng{list of the integer vectors}%
  \call{\Mtype{nonnegative integer} n, \Mtype{nonnegative integer} k
    \Mopt{, constraints}}%
  \eng{\begin{sloppypar}
    Returns the list of the integer vectors of sum \Mpar{n} with
    \Mpar{k} parts satisfying \Mpar{constraints}.
       \end{sloppypar}}
\end{MMethodDetails}

\begin{MMethodDetails}{first}
  \infoEng{first integer vector}%
  \call{\Mtype{nonnegative integer} n, \Mtype{nonnegative integer} k
    \Mopt{, constraints}}%
  \eng{Returns the first integer vector of sum \Mpar{n} with \Mpar{k}
    parts satisfying \Mpar{constraints} or \Mex{FAIL} if there is
    none.}
\end{MMethodDetails}
    
\begin{MMethodDetails}{Next}
  \infoEng{next integer vector}%
  \call{\Mtype{integer vector} v \Mopt{, constraints}}%
  \eng{Returns the integer vector following \Mpar{v} satisfying
    \Mpar{constraints} or \Mex{FAIL} if there is none.}
\end{MMethodDetails}

\begin{MExample}{ex-basic}
  \eng{There are $15$ integer vectors of sum $4$ with $3$ parts:}
  \begin{Mexin}
combinat::integerVectors::count(4, 3)
  \end{Mexin}
  \begin{Mexout}
                              15
  \end{Mexout}

  \eng{Here is the list:}
  \begin{Mexin}
combinat::integerVectors::list(4, 3)
  \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{You can use the function \Mex{combinat::integerVectors::first}
    to get the ``first'' integer vector of a given sum:}
  \begin{Mexin}
combinat::integerVectors::first(4, 3)
  \end{Mexin}
  \begin{Mexout}
                           [4, 0, 0]
  \end{Mexout}
  
  \eng{Using \Mex{combinat::integerVectors::Next}, you can calculate
    the ``next'' integer vector.  This function takes as argument the
    integer vector relative to which you want the next one:}
  \begin{Mexin}
combinat::integerVectors::Next([4, 0, 0])
  \end{Mexin}
  \begin{Mexout}
                           [3, 1, 0]
  \end{Mexout}
  
  \eng{\Mex{combinat::integerVectors::Next} returns \Mup{FAIL} when
    the last integer vector is given in the input:}
  \begin{Mexin}
combinat::integerVectors::Next([0, 0, 4])
  \end{Mexin}
  \begin{Mexout}
                             FAIL
  \end{Mexout}
  
  \eng{If you want to run through the integer vectors of a given sum,
    you can generate them one by one to save memory:}
  \begin{Mexin}
g := combinat::integerVectors::generator(2, 2):
g(); g(); g(); g();
  \end{Mexin}
  \begin{Mexout}
                            [2, 0]

                            [1, 1]

                            [0, 2]

                             FAIL
  \end{Mexout}

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

                            [1, 1]

                            [0, 2]
  \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 integer vectors having only small entries. This is the list of
    the integer vectors of sum $4$ with all parts at most $2$:}
  \begin{Mexin}
combinat::integerVectors::list(4, 3, MaxPart=2)
  \end{Mexin}
  \begin{Mexout}
[[2, 2, 0], [2, 1, 1], [2, 0, 2], [1, 2, 1], [1, 1, 2],

   [0, 2, 2]]
  \end{Mexout}
  
  \eng{\MinPart\ is complementary to \MaxPart\ and selects integer vectors
    having only large parts (it takes a non-negative value). This is
    the list of the integer vectors of sum $4$ with all parts at least $1$:}
  \begin{Mexin}
combinat::integerVectors::list(4, 3, MinPart=1)
  \end{Mexin}
  \begin{Mexout}
               [[2, 1, 1], [1, 2, 1], [1, 1, 2]]
  \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
    inclusion constraints. This is the list of the integer vectors
    of $4$ upper bounded by \Mex{[3, 1, 2]}:}
  \begin{Mexin}
combinat::integerVectors::list(4, 3, Outer=[3, 1, 2])
  \end{Mexin}
  \begin{Mexout}
    [[3, 1, 0], [3, 0, 1], [2, 1, 1], [2, 0, 2], [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 the integer vectors
    of sum $4$ and of length at most $3$ such that the first and third
    parts are at most $1$:}
  \begin{Mexin}
combinat::integerVectors::list(4, 3, Outer=[1, infinity, 1])
  \end{Mexin}
  \begin{Mexout}
         [[1, 3, 0], [1, 2, 1], [0, 4, 0], [0, 3, 1]]
  \end{Mexout}
  
  \eng{This is the list of the integer vectors of sum $4$ lower bounded by
    \Mex{[1, 1, 1]}:}
  \begin{Mexin}
combinat::integerVectors::list(4, 3, Inner=[1, 1, 1])
  \end{Mexin}
  \begin{Mexout}
               [[2, 1, 1], [1, 2, 1], [1, 1, 2]]
  \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 integer vectors of sum $4$ with $3$ parts:}
  \begin{Mexin}
combinat::integerVectors::list(4, 3, MinSlope=0)
  \end{Mexin}
  \begin{Mexout}
         [[1, 1, 2], [0, 2, 2], [0, 1, 3], [0, 0, 4]]
  \end{Mexout}
  
  \eng{This is the list of the integer vectors of sum $4$ with $3$
    parts such that two consecutive parts differ by at most one unit:}
  \begin{Mexin}
combinat::integerVectors::list(4, 3, MinSlope=-1, MaxSlope=1)
  \end{Mexin}
  \begin{Mexout}
               [[2, 1, 1], [1, 2, 1], [1, 1, 2]]
  \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 the integer vectors of sum $11$ with $3$
    parts between $2$ and $5$ such that the difference between two
    consecutive parts is between $-2$ and $2$:}
  \begin{Mexin}
combinat::integerVectors::list(11, 3,
                               MinSlope=-2, MaxSlope=2,
                               MinPart=2, MaxPart=5)
  \end{Mexin}
  \begin{Mexout}
[[5, 4, 2], [5, 3, 3], [4, 4, 3], [4, 3, 4], [3, 5, 3],

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

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

\begin{MExample}{ex-constraints-monomial}
  \eng{We demonstrate how to generate the monomials in the variables
    \Mex{x,y,z} of total degree $6$ which are divisible by \Mex{x^2z} and
    divide \Mex{x^5yz^2}}
  \begin{Mexin}
map(combinat::integerVectors::list(6, 3, Inner=[2,0,1], 
Outer=[5,1,2]), v -> expr(poly([[1,v]], [x,y,z])))
  \end{Mexin}
  \begin{Mexout}
                  5     4       4  2   3    2
                [x  z, x  y z, x  z , x  y z ]
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-constraints-motzkin}
  \eng{We demonstrate how to generate the Motzkin words of a given
    length \Mex{k}. A Motzkin word is a list of $-1$, $0$, and $1$ of
    length \Mex{n} such that all partial sums are nonnegative and the
    total sum is zero. Geometrically, this is a discrete path in the
    integer plane $N\times N$ starting at $(0,0)$ with right-down,
    right and right-up steps, and ending at $(n,0)$. We work on the
    list of the \Mex{k+1} partial sums, and use the option \Outer\ to
    force the first and last one to be zero. Note that \Outer\ itself
    is required to satisfy the slope constraints. We also disregard
    the sum \Mex{s} of the partial sums. Here is the list of the
    Motzkin words of length 5:}
  \begin{Mexin}
map(_concat(combinat::integerVectors::list(s, 6,
                   MinSlope=-1, MaxSlope=1,
                   Outer=[0, 1, 2, 2, 1, 0]) $ s=0..7),
    l -> [l[i+1]-l[i] $ i=1..nops(l)-1])
  \end{Mexin}
  \begin{Mexout}
[[0, 0, 0, 0, 0], [1, -1, 0, 0, 0], [0, 1, -1, 0, 0],

   [0, 0, 1, -1, 0], [0, 0, 0, 1, -1], [1, 0, -1, 0, 0],

   [1, -1, 1, -1, 0], [1, -1, 0, 1, -1], [0, 1, 0, -1, 0],

   [0, 1, -1, 1, -1], [0, 0, 1, 0, -1], [1, 0, 0, -1, 0],

   [1, 0, -1, 1, -1], [1, -1, 1, 0, -1], [0, 1, 0, 0, -1],

   [1, 1, -1, -1, 0], [1, 0, 0, 0, -1], [0, 1, 1, -1, -1],

   [1, 1, -1, 0, -1], [1, 0, 1, -1, -1], [1, 1, 0, -1, -1]]
  \end{Mexout}
  \eng{A similar trick can be used to generate Dyck words instead.
    Here is the list of Dyck words of length $2\times4$:}
  \begin{Mexin}
map(_concat(combinat::integerVectors::list(s, 9,
                       MinSlope=0, MaxSlope=1,
                       Inner=[0, 1, 1, 2, 2, 3, 3, 4, 4],
                       Outer=[0, 1, 2, 3, 4, 4, 4, 4, 4]
                               ) $ s=20..26),
    l -> combinat::dyckWords::toString
      ([if l[i+1]=l[i] then 0 else 1 end_if $ i=1..nops(l)-1]))
  \end{Mexin}
  \begin{Mexout}
["()()()()", "(())()()", "()(())()", "()()(())", "(()())()",

   "(())(())", "()(()())", "((()))()", "(()()())", "()((()))",

   "((())())", "(()(()))", "((()()))", "(((())))"]
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-constraints-k-partitions}
  \eng{We show here how to generate the \emph{ordered
      \Mex{k}-partitions} of an integer vector \Mex{m}; that is the
    lists of \Mex{k} integer vectors \Mex{m1,...,mk} such that
    \Mex{m1+...+mk=m}; or the \Mex{k x nops(m)} matrix with prescribed
    column sums given by \Mex{m}.
  
    We can build for each part \Mex{m[i]} of \Mex{m} a generator for
    the integer vectors of sum \Mex{m[i]} with \Mex{k} parts, and take
    the cartesian product of those generators. Note that this yields
    lists of \Mex{l} lists of \Mex{k} integers instead of lists of
    \Mex{k} lists of \Mex{l} integers, so we need to further
    transpose the lists.
  
    Let's take an example, with \Mex{m:=[1,3,2]} and \Mex{k:=2}. The
    first part yields the lists \Mex{[1,0]} or \Mex{[0,1]}, the second
    \Mex{[3,0]}, \Mex{[2,1]}, \Mex{[1,2]}, or \Mex{[0,3]} and the last
    part yields \Mex{[2,0]}, \Mex{[1,1]}, \Mex{[0,2]}.  The first
    element of the cartesian product is \Mex{[[1,0], [3,0],[2,0]]},
    and after transposition we get \Mex{[[1,3,2],[0,0,0]]}.
    
    Now, here is the code:}
  \begin{Mexin}
orderedIntegerVectorPartitionsGenerator :=
proc(m: combinat::integerVectors, k: Type::PosInt)
    option escape;
begin
    combinat::generators::map
    (// The cartesian product of the generators of integer vectors
     combinat::generators::cartesian
	(combinat::integerVectors::generator(m[i], k) $ i=1..nops(m)),
     // A function that does the transposition
     l->[[l[j][i] $ j=1..nops(m)] $ i=1..k]);
end_proc:
g := orderedIntegerVectorPartitionsGenerator([1,3,2], 2):
g(), g(), g(), g(), g();
  \end{Mexin}
  \begin{Mexout}
[[1, 3, 2], [0, 0, 0]], [[1, 3, 1], [0, 0, 1]],

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

   [[1, 2, 1], [0, 1, 1]]
  \end{Mexout}
  \eng{Alltogether, there are \Mex{2*4*3=24} ordered $2$-partitions of
    \Mex{[1,3,2]}:}
  \begin{Mexin}
g := orderedIntegerVectorPartitionsGenerator([1,3,2], 2):
combinat::generators::count(g);
  \end{Mexin}
  \begin{Mexout}
                              24
  \end{Mexout}
%$
  \eng{\begin{sloppypar}
    As an application, this can be used to generate the
    \emph{ordered \Mex{k}-partitions} of a multiset \Mex{s}; that is
    the lists of \Mex{k} multisets \Mex{s1,...,sk} whose union is
    \Mex{s}; for example, \Mex{[\{a,b,b,b,c\}, \{a,b,d\}]} and
    \Mex{[\{a,b,d\}, \{a,b,b,b,c\}]} are two distinct partitions of
    the multiset \Mex{\{a,a,b,b,b,b,c,d\}}.
    \end{sloppypar}
    
    Indeed, a multiset \Mex{s} such as \Mex{\{a,a,b,b,b,b,c,d\}} can be
    represented by the integer vector \Mex{m} of its repetitions, here
    \Mex{[2,4,1,1]}. Now, partitioning \Mex{s} in \Mex{k} multisets is
    equivalent to finding \Mex{k} integer vectors \Mex{m1,...,mk} that
    sum up to \Mex{m} as above. We leave as an exercise for the reader to
    build the appropriate conversion routines and to derive a generator for
    ordered multiset partitions (hint: use
    \Mup{combinat::generators::map}).}
\end{MExample}

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

\MSuperDomain{combinat::words}

\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: 
