% $Id: integerListsLexTools.tex,v 1.1.1.5 2004/10/04 17:25:16 nthiery Exp $
\begin{Mhelppage}{integerListsLexTools}{F.~Hivert and N.~Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
\Mproofread{descouens}{10/2003}{proofread}
% TODO: warning about incorrect results when the input is inconsistent!

\begin{MInfo}
  \eng{lexicographic generation of lists of integers}
\end{MInfo}

\begin{MIntro}
  \eng{The library \Mthis{} provides functions for the lexicographic
    generation of lists of integers under length, upper/lower bounds,
    and regularity constraints.}
    
  \eng{\Mwarn{This is an internal library. It is used by the special
      purpose libraries \Mup{combinat::partitions},
      \Mup{combinat::compositions}, and \Mup{combinat::integerVectors}
      which provide user-friendly interfaces.
    
      This documentation is only provided here for the curious reader
      as well as for developers. The interface has been designed with
      efficiency in mind (no type checking, ...), and is subject to
      incompatible changes anytime in the future. Use at your own
      risk.}}
  
  \eng{\Mwarn{With the current algorithm, the constraints should
      satisfy the following conditions:
      \begin{itemize}
      \item The upper and lower bounds themselves should satisfy the
        regularity constraints.
      \item The maximal and minimal slopes values should not be equal.
      \item The maximal and minimal part values should not be equal.
      \end{itemize}
      Those conditions are not checked by the algorithm, and the
      result may be completely incorrect if they are not satisfied.}}
\end{MIntro}

\MKeywords{combinatorics}

\begin{MDetails}
  \eng{Here, we call \emph{integer list} a list \Mex{l} of nonnegative
    integers, its \emph{parts}. By abuse, infinite parts will be
    allowed in some cases. The \emph{length} of \Mex{l} is the number
    of its parts; the \emph{sum} of \Mex{l} is the sum of its parts.}
  
  \eng{Let \Mex{minSlope} be an integer or $\Mex{-infinity}$ and
    \Mex{maxSlope} be an integer or $\Mex{+infinity}$. Then an integer
    list is \emph{regular} w.r.t. \Mex{minSlope} and \Mex{maxSlope} if
    \Mex{minSlope <= l[i+1]-l[i] <= maxSlope}, for all \Mex{i}.
    Regular functions are defined similarly.}
  
  \eng{Let \Mex{f} be a function, and \Mex{l} an integer list. Then,
    \Mex{f} is an \emph{upper bound} (resp. \emph{lower bound}) for
    \Mex{l} if \Mex{l[i]<=f(i)} (resp. \Mex{f(i)<=l[i]}) for all
    \Mex{i}.}
  
  \eng{A set of constraints is specified by a sequence of $6$ objects
    \Mex{minLength, maxLength, floor, ceiling, minSlope, maxSlope} of
    the following types:
    \begin{itemize}
    \item \Mex{minLength}: nonnegative integer;
    \item \Mex{maxLength}: nonnegative integer or \Mex{+infinity};
    \item \Mex{floor} and \Mex{ceiling}: regular functions from
      \Mex{[1..maxLength]} to \Mex{0..+infinity};
    \item \Mex{minSlope}: integer or \Mex{-infinity};
    \item \Mex{maxSlope}: integer or \Mex{+infinity}.
    \end{itemize}
    
    The purpose of this library is to generate all the \emph{valid}
    integer lists of a given sum which satisfy all the specified
    constraints. }
  
  \eng{\Mwarn{Two valid integer lists are considered equivalent if
      they only differ by trailing zeroes at positions. In this case,
      only the list with the least number of trailing zeroes will be
      generated.}}
\end{MDetails}

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


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

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

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

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

\begin{MExample}{ex-basic}
  \eng{There are $5$ partitions of $4$:}
  \begin{Mexin}
combinat::integerListsLexTools::count(
    4, 0, infinity, ()->0, ()->infinity, -infinity, 0)
  \end{Mexin}
  \begin{Mexout}
                               5
  \end{Mexout}

  \eng{Here is the list:}
  \begin{Mexin}
combinat::integerListsLexTools::list(
    4, 0, infinity, ()->0, ()->infinity, -infinity, 0)
  \end{Mexin}
  \begin{Mexout}
        [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
  \end{Mexout}
  
  \eng{This is the list of all partitions of $7$ with parts at least
    $2$:}
  \begin{Mexin}
combinat::integerListsLexTools::list(
    7, 0, infinity, ()->2, ()->infinity, -infinity, 0)
  \end{Mexin}
  \begin{Mexout}
               [[7], [5, 2], [4, 3], [3, 2, 2]]
  \end{Mexout}
  
  \eng{This is the list of all partitions of $5$ which are bounded
    above by \Mex{p:=[3,2,2]}:}
  \begin{Mexin}
p:=[3,2,2]:
combinat::integerListsLexTools::list(
    5, 0, nops(p), ()->0, i->p[i], -infinity, 0)
  \end{Mexin}
  \begin{Mexout}
                [[3, 2], [3, 1, 1], [2, 2, 1]]
  \end{Mexout}

  \eng{This is the list of all partitions of $5$ which are bounded below by
    \Mex{p:=[2,1,1]}:}
  \begin{Mexin}
p:=[2,1,1]:
combinat::integerListsLexTools::list(
    5, 0, nops(p), i->p[i], ()->+infinity, -infinity, 0)
  \end{Mexin}
  \begin{Mexout}
          [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1]]
  \end{Mexout}

  \eng{This is the list of all compositions of $4$:}
  \begin{Mexin}
combinat::integerListsLexTools::list(
    4, 0, infinity, ()->1, ()->infinity, -infinity, infinity)
  \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{This is the list of all integer vectors of sum $3$ and length $3$:}
  \begin{Mexin}
combinat::integerListsLexTools::list(
    3, 3, 3, ()->0, ()->infinity, -infinity, infinity)
  \end{Mexin}
  \begin{Mexout}
[[3, 0, 0], [2, 1, 0], [2, 0, 1], [1, 2, 0], [1, 1, 1],

   [1, 0, 2], [0, 3, 0], [0, 2, 1], [0, 1, 2], [0, 0, 3]]
  \end{Mexout}
  
  \eng{This is the list of all monomials of degree $4$ which divide the
    monomial \Mex{x^3y^1z^2} (a monomial being represented by its
    degree vector):}
  \begin{Mexin}
R:=Dom::DistributedPolynomial([x,y,z]):
m:=[3,1,2]:
map(combinat::integerListsLexTools::list(
        4, nops(m), nops(m), ()->0, i->m[i], -infinity, infinity),
    m1->R([[1,m1]]))
  \end{Mexin}
  \begin{Mexout}
                3     3     2       2  2       2
              [x  y, x  z, x  y z, x  z , x y z ]
  \end{Mexout}
  
\end{MExample}

\begin{MExample}{ex-degeneracy}
  \eng{If \Mex{maxLength=infinity} and \Mex{maxSlope>0}, testing
    whether there exists a valid integer list of sum \Mex{n} may be
    only semi-decidable. In the following example, the algorithm will
    enter an infinite loop, because it needs to decide whether
    \Mex{ceiling(i)} is nonzero for some \Mex{i}:}
  \begin{Mvin}{test=false}
combinat::integerListsLexTools::first(
    1, 0, infinity, ()->0, ()->0, -infinity, infinity)
  \end{Mvin}
\end{MExample}

\begin{MBackground}
  \eng{Except for one degenerate case where the algorithm may run
    forever without producing anything (see
    example~\ref{ex-degeneracy}), the complexity of the generation
    algorithm is constant time amortized for each integer list
    produced.}
  
  \eng{The generation algorithm could be extended to deal with
    non-constant slope constraints and with negative parts, as well as
    to accept a range parameter instead of a single integer for the
    sum \Mpar{n} of the lists. Let us know if those would be useful
    features.}
  
  \eng{\Mwarn{Counting is done by brute force generation.}}
\end{MBackground}

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

\end{Mhelppage}

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