% $Id: preface.tex,v 1.1.1.8 2004/10/21 15:52:51 nthiery Exp $
\section*{The library \Mex{combinat}}

\eng{
  The \Mex{combinat} library provides combinatorial functions, as well as
  tools for counting, generating, and manipulating combinatorial
  objects.
  
  It consists of a subset of the algebraic combinatorics contribution
  package \mupad-Combinat version 1.0. The full featured package, when
  installed, can be loaded with:
  \begin{Mvin}{test=false}
package("Combinat")
  \end{Mvin}
  See \texttt{http://mupad-combinat.sourceforge.net/} for details.
  
  The library functions are called using the library name
  \Mex{combinat} and the name of the function. E.g., use
  \begin{Mvin}{test=false}
combinat::bell(5)
  \end{Mvin}
  to compute the $5$-th Bell number. This mechanism avoids naming
  conflicts with other library functions.
  
  If this is found to be inconvenient, then the routines of the
  \Mex{combinat} library may be exported via \Mup{export}. E.g.,\ 
  after calling
  \begin{Mvin}{test=false}
export(combinat, bell)
  \end{Mvin}
  the function \Mex{combinat::bell} may be called directly:
  \begin{Mvin}{test=false}
bell(5)
  \end{Mvin}
  All routines of the \Mex{combinat} library are exported
  simultaneously by
  \begin{Mvin}{test=false}
export(combinat)
  \end{Mvin}
  
  The functions and sub-libraries available in the \Mex{combinat}
  library can be listed using
  \begin{Mvin}{test=false}
info(combinat)
  \end{Mvin}
}

\eng{\subsection*{Structure of the library}}

%TODO: fix progressively the indentation below
  \eng{The library package contains three different sorts of features:
    functions for computing classical sequences of numbers, domains called
    \emph{combinatorial classes} of classical combinatorial objects including
    functions for counting and generating and manipulating these objects and
    finally libraries of handy tools including highly versatile and
    configurable algorithms for generating various classes of objects.}
    
  \eng{\begin{sloppypar} The most important part of the \Mup{combinat}
      library, \textit{i.e.\/} the part devoted to combinatorial objects, is
      organized in separate domains with similar interfaces, one for each
      combinatorial class. For example,
      \Mup{combinat::cartesianProduct::count} is used to determine the number
      of elements in a cartesian product, while \Mup{combinat::subsets::count}
      returns the number of subsets of a set. The following domains are
      provided:
    \end{sloppypar}

    \begin{itemize}
    \item \Mup{combinat::partitions} provides functions dealing with
      partitions, \textit{i.e.\/}, decreasing lists of natural numbers with a fixed sum.
    \item \Mup{combinat::skewPartitions} provides functions dealing with skew
      partitions, \textit{i.e.\/}, a pair of two partitions, where the second partition
      is a inner partition of the first.
    \item \Mup{combinat::compositions} deals with compositions of natural
      numbers, \textit{i.e.\/}, with lists of natural numbers with a fixed sum.
    \item \Mup{combinat::integerVectors} deals with vectors of nonnegative
      integers of fixed length and fixed sum.
    \item \Mup{combinat::integerVectorsWeighted} is similar, but the sum is
      replaced by a weighted sum.

    \item \Mup{combinat::cartesianProduct} provides functions dealing with the
      Cartesian product of a finite number of sets or lists.
    \item \Mup{combinat::subsets} deals with subsets of a set.

    \item \Mup{combinat::words} deals with words, \textit{i.e.\/}, lists of
      fixed length consisting of elements of a specified alphabet.
    \item \Mup{combinat::subwords} deals with subwords: Starting with a given
      list, delete any number of entries.
    \item \Mup{combinat::permutations} works on permutations of lists and also
      standard permutations (\textit{i.e.\/} permutations of $\{1,\dots,n\}$).
    \item \Mup{combinat::dyckWords} deals with Dyck words. These can be
      interpreted as words of well balanced parentheses.
    \item \Mup{combinat::necklaces} and \Mup{combinat::lyndonWords}
      allow for generating (aperiodic) words up to cyclic rotations.

    \item \Mup{combinat::integerMatrices} deals with matrices of nonnegative
      integers of fixed sum for rows and columns.
    \item \Mup{combinat::tableaux}, \Mup{combinat::skewTableaux},
      \Mup{combinat::ribbons} provides utilities for tableaux, skew
      tableaux, and tableaux of ribbon shape respectively. Those
      objects are fundamental, among other things, in the
      representation theory of the symmetric group and for computing
      with symmetric functions and polynomials.
    \item \Mup{combinat::ribbonsTableaux} deals with ribbon tableaux,
      which appear when studying $q$-analogues of symmetric functions.

    \item \Mup{combinat::decomposableObjects} deals with objects that can be
      described recursively by a grammar.
    \item \Mup{combinat::trees} provides functions to generate and manipulate
      trees.
    \item \Mup{combinat::binaryTrees} and
      \Mup{combinat::labelledBinaryTrees} provides functions to
      generate and manipulate (labelled) binary trees.
    \item \Mup{combinat::graphs} provides an interface with the
      \Mex{C++} library \Mex{Nauty} for generating unlabelled simple
      graphs.

    \item \Mup{combinat::linearExtensions} provides functions to enumerate
      linear extensions of partially ordered sets.
    \end{itemize}
  }

\eng{Some of the previous combinatorial classes provide further sub-domains,
  this feature should be extensively extended in the future:
  \begin{itemize}
  \item \Mup{combinat::binaryTrees}:
    \begin{itemize}
    \item \Mup{combinat::binaryTrees::fromSaillance}
      for enumerating binaryTrees by saillance.
    \item \Mup{combinat::binaryTrees::shuffle} with
      utilities for the shuffle product of two binary trees.
    \end{itemize}
  \item \Mup{combinat::compositions}:
    \begin{itemize}
    \item \Mup{combinat::compositions::finer} to deal
      with compositions finer than a given one;
    \item \Mup{combinat::compositions::fatter} to deal
      with compositions fatter than a given one;
    \item \Mup{combinat::compositions::finerVectors} to
      deal with integer vectors finer than a given composition;
    \end{itemize}
  \item \Mup{combinat::words}:
    \begin{itemize}
    \item \Mup{combinat::words::fromStandard} to enumerate
      words with a given standard permutations;
    \item \Mup{combinat::words::shuffle} to compute the
      shuffle of two words.
    \end{itemize}
\end{itemize}
}

\eng{Many of the combinatorial classes are \emph{facade domains}:
  their objects are represented using elements of basic \mupad{}
  domains. For example, \Mup[combinat,permutations]{permutations} are
  represented using plain lists of integers (of the domain
  \Mup{DOM_LIST}). In particular, no constructor needs to be called to
  create such objects.}

\eng{Objects of the other non-facade combinatorial classes are
  constructed with the standard \mupad{} idiom: \Mex{cl(objdesc)}
  constructs the object of the class \Mex{cl} whose description is
  \Mex{objdesc}. For example
  \Mex{combinat::labelledBinaryTrees([a,[b],[c]])} constructs a
  labelled binary tree with three nodes labelled \Mex{a,b,c}.  The
  combinatorial class that are not facade domain are
  \begin{itemize}
  \item \Mup{combinat::trees}, \Mup{combinat::binaryTrees},
    \Mup{combinat::labelledBinaryTrees};
  \item \Mup{combinat::tableaux}, \Mup{combinat::skewTableaux},
    \Mup{combinat::ribbons} (beware: in former \texttt{MuPAD-Combinat
      releases}, \Mup{combinat::tableaux} used to be a facade
    domain!);
  \item \Mup{combinat::ribbonsTableaux}.
  \end{itemize}
}


  \eng{\subsection*{Standard interface}}
  
\eng{To provide default implementations and to ensure that the interfaces are
  compatible, all combinatorial domains belong to the category
  \Mup{Cat::CombinatorialClass}. The purpose of this category is to specify
  the behavior of several standardized functions. Note that a specific
  combinatorial class does not need to implement all these functions. The
  category \Mup{Cat::CombinatorialClass} also provides default implementations
  (possibly inefficient) for some of these.}

\eng{Here are the list and the meanings of these standard functions:
  \noindent
  \begin{longtable}{ll}
    \Mex{isA(\Mpar{object}, \Mopt{size})}
      & is an object an element of the class (of size \Mex{size})\\
    \Mex{size(\Mpar{object})}
      & size of the object \Mex{object}\\
    \Mex{count(\Mopt{size})}
      & number of objects (of size \Mex{size})\\
    \Mex{generatingSeries(s, \Mopt{ident})}
      & generating series by size\\
    \Mex{generator(\Mopt{size})}
      & generator for all the objects (of size \Mex{size})\\
    \Mex{list(\Mopt{size})}
      & list of all the objects (of size \Mex{size})\\
    \Mex{first(\Mopt{size})}
      & first object (of size \Mex{size}) or \Mup{FAIL}\\
    \Mex{last(\Mopt{size})}
      & last object (of size \Mex{size}) or \Mup{FAIL}\\
    \Mex{Next(s)}
      & next object after \Mex{s} or \Mup{FAIL}\\
    \Mex{previous(s)}
      & previous object before \Mex{s} or \Mup{FAIL}\\
    \Mex{rank(s)}
      & rank of the object \Mex{s}\\
    \Mex{unrank(r\Mopt{, size})}
      & \Mex{r}-th object (of size \Mex{size}), or \Mup{FAIL}\\
    \Mex{random(\Mopt{size})}
      & random object (of size \Mex{size}) or \Mup{FAIL}\\
    \Mex{_less(s1, s2)}
      & comparison of the objects \Mex{s1} and \Mex{s2}
  \end{longtable}
  Note that \Mex{Next} is capitalized because \Mex{next} is a reserved
  keyword in \mupad{}.}

\eng{Note also that, in most packages, these functions take some other
  optional arguments. In this case, the functions \Mex{isA},
  \Mex{count}, \Mex{list}, and \Mex{generator} accept the same
  arguments.}
\medskip

\eng{For most combinatorial classes \Mex{cl}, the call \Mex{cl(\Mpar{size})}
  is a shortcut for \Mex{cl::list(\Mpar{size})}; this feature is solely
  provided as a syntactic sugar for interactive use; please do not use it in
  programs! In particular for the non-facade domains this shortcut may be
  ambiguous with the creation of the objects of the domain and thus may be
  disabled.}
\medskip

\eng{In a near future, we plan to add functions to manipulate
  combinatorial classes, for example to construct subclasses of a
  given class.  So it is very important to stick closely to these
  conventions.}
\bigskip

\eng{ The following methods are implemented in more than one of those
  libraries:}
% OUTDATED!
\bigskip\noindent
\begin{tabular}{@{}p{8em}*{11}{@{\ }c}@{}}
  \toprule
  % \Mex{size}, \Mex{testtype}, generatingSeries, rank, unrank, ...
   & \Mex{count} & \Mex{generator} & \Mex{list} &
  \Mex{first} & \Mex{last} & \Mex{Next} & \Mex{previous} &
  \Mex{rank} &\Mex{unrank} & \Mex{random} \\\midrule
  \Mex{partitions}      &  + &  + &  + &  + & -- &  + & -- & -- & -- & --\\
  \Mex{skewPartitions}  &  + &  + &  + & -- & -- & -- & -- & -- & -- & --\\
  \Mex{compositions}    &  + &  + &  + &  + & -- &  + & -- & -- & -- & --\\
  \Mex{integerMatrices} &  + &  + &  + & -- & -- & -- & -- & -- & -- & --\\
  \Mex{integerVectors}  &  + &  + &  + &  + & -- &  + & -- & -- & -- & --\\
  \Mex{integerVectors}\-\Mex{Weighted}
                        &  + &  + &  + &  + & -- &  + & -- & -- & -- & --\\
  \Mex{integerLists}\-\Mex{LexTools}
                        & -- &  + &  + &  + & -- &  + & -- & -- & -- & --\\
  \Mex{cartesianProduct}&  + &  + &  + & -- & -- & -- & -- & -- & -- & --\\
  \Mex{subsets}         &  + &  + &  + &  + &  + & -- & -- & -- & -- & --\\
  \Mex{permutations}    &  + &  + &  + &  + &  + &  + &  + & -- & -- &  +\\
  \Mex{words}           &  + &  + &  + & -- & -- & -- & -- & -- & -- & --\\
  \Mex{subwords}        &  + &  + &  + &  + &  + & -- & -- & -- & -- & --\\
  \Mex{dyckWords}       &  + &  + &  + & -- & -- & -- & -- & -- & -- & --\\
  \Mex{nonCrossing}\-\Mex{Partitions}
                        & -- & -- & -- & -- & -- & -- & -- & -- & -- & --\\
  \Mex{tableaux}        &  + &  + &  + & -- & -- & -- & -- & -- & -- & --\\
  \Mex{decomposable}\-\Mex{Objects}
                        &  + &  + &  + & -- & -- & -- & -- & -- &  + &  +\\
  \Mex{trees}
                        &  + &  + &  + & -- & -- & -- & -- & -- &  + &  +\\
  \Mex{binaryTrees}
                        &  + &  + &  + & -- & -- & -- & -- & -- &  + &  +\\
  \bottomrule
\end{tabular}
\bigskip


\eng{
  \begin{sloppypar}
    Many of the sub-libraries provide further methods, such as
    \Mup{combinat::permutations::inverse}. See the corresponding
    documentation for details.
  \end{sloppypar}
}

  \eng{
  The \Mup{combinat} library also contains the following support
  sub-libraries, which are used intensively by the previous ones.
  \begin{enumerate}
  \item \Mup{combinat::generators} provides utilities for creating and
    manipulating generators, \textit{i.e.\/}, functions which, on each call,
    return the next element of a (possibly infinite) sequence of
    values.
    \item \Mup{combinat::integerListsLexTools} provides an algorithm for
      generating, in lexicographic order, lists of natural numbers
      satisfying certain constraints.
  \end{enumerate}
  
  Finally some classical combinatorial sequences of numbers are provided:
  \begin{enumerate}
    \item \Mup{combinat::bell}: Bell numbers;
    \item \Mup{combinat::catalan}: Catalan numbers;
    \item \Mup{combinat::stirling1}: Stirling numbers of the first kind;
    \item \Mup{combinat::stirling2}: Stirling numbers of the second kind;
    \item \Mup{combinat::modStirling}: Modified Stirling numbers;
  \end{enumerate}
}

\eng{\subsection*{Categories}}

\eng{ 
  The \Mup{combinat} library is articulated around four main categories:

  \begin{enumerate}
  \item \Mup{Cat::CombinatorialClass}, which is the basic category for
    combinatorial objects. It provides basic functions for types
     \begin{itemize}
     \item \Mex{isA}, 
     \item \Mex{testtype}
     \end{itemize}
     and default implementations for the standard combinatorial functions for
     counting, generating and listing elements in combinatorial classes:
    \begin{itemize}
    \item \Mex{count},
    \item \Mex{generator}
    \item \Mex{list}
    \end{itemize}
  \item \Mup{Cat::GradedCombinatorialClass} which is the category of
    combinatorial objects whose size is a nonnegative integer. In particular
    the calls \Mex{count(n)}, \Mex{generator(n)}, \Mex{list(n)} for any
    integer \Mex{n} are meaningful.  It is a sub-category of the category
    \Mup{Cat::CombinatorialClass}.
  \item
%    \begin{sloppypar}
      \Mex{Cat::DecomposableClass} is used as a front-end category for
    combinatorial classes based on the domain
    \Mup{combinat::decomposableObjects}, and is devoted to objects that can be
    described by some recursive grammar. This category is a subcategory of
    \Mup{Cat::GradedCombinatorialClass}, and it provides also by default these two
    more functions:
%  \end{sloppypar}
     \begin{itemize}
     \item \Mex{unrank}, 
     \item \Mex{random}
     \end{itemize}
   \item \Mup{Cat::IntegerListsLexClass} is used as a front-end category for
     combinatorial classes based on \Mup{combinat::integerListsLexTools}, and
     is devoted to lexicographic enumerations of list of integers with a fixed
     sum and some prescribed constraints. It is a subcategory of
     \Mup{Cat::GradedCombinatorialClass} and provide also by default the functions:
    \begin{itemize}
    \item \Mex{first}, 
    \item \Mex{Next},
    \item \Mex{_less}
    \end{itemize}
  \end{enumerate}
}

\eng{Most of the libraries are in one of those categories (except
  \Mup{combinat::generators} and famous numbers: Bell, Catalan,
  Stirling, ...).

  Here is a classification:
  \begin{itemize}
    \item \Mup{Cat::CombinatorialClass}
    \begin{enumerate} 
      \item \Mup{combinat::binaryTrees::fromSaillance}
      \item \Mup{combinat::binaryTrees::shuffle}
      \item \Mup{combinat::cartesianProduct}
      \item \Mup{combinat::compositions::finer}
      \item \Mup{combinat::compositions::fatter}
      \item \Mup{combinat::compositions::finerVectors}
      \item \Mup{combinat::integerListsLexTools} 
      \item \Mup{combinat::integerMatrices}
      \item \Mup{combinat::integerVectorsWeighted}
      \item \Mup{combinat::linearExtensions} 
      \item \Mup{combinat::tableaux} 
      \item \Mup{combinat::words::fromStandard}
      \item \Mup{combinat::words::shuffle}
      \item \Mup{combinat::subsets} 
      \item \Mup{combinat::subwords}
      \item \Mup{combinat::words}
    \end{enumerate}
    \item \Mup{Cat::GradedCombinatorialClass}
    \begin{enumerate} 
      \item \Mup{combinat::nonCrossingPartitions}
      \item \Mup{combinat::permutations}
      \item \Mup{combinat::skewPartitions}
      \item \Mup{combinat::tableaux}
    \end{enumerate}
    \item \Mex{Cat::DecomposableClass}
    \begin{enumerate}
      \item \Mup{combinat::binaryTrees}
      \item \Mup{combinat::decomposableObjects}
      \item \Mup{combinat::dyckWords}
      \item \Mup{combinat::labelledBinaryTrees}
      \item \Mup{combinat::trees}
    \end{enumerate}
    \item \Mup{Cat::IntegerListsLexClass}
    \begin{enumerate}
      \item \Mup{combinat::compositions}
      \item \Mup{combinat::integerVectors}
      \item \Mup{combinat::partitions}
    \end{enumerate}
  \end{itemize}}

\eng{\subsection*{Examples}}

\eng{In this section, we pick a few sample applications at random.
  First, we \Mhref[stdlib,export]{export} the \Mup{combinat} library
  to save us some typing:}%
\begin{Mexin}
export(combinat):
\end{Mexin}
\eng{Note that the sub-libraries such as \Mup{combinat::partitions}
  are \emph{not} intended to be exported.}

\eng{In our first examples, we use the abbreviated calls for list
  generation. We generate the Cartesian product of three lists, we
  compute all permutations of the numbers $1, 2, 3$, and we ask for
  all sub-words of the word \Mex{[a, b, c, d]}:}
\begin{Mexin}
cartesianProduct([1,2,3],[a,b],[i,ii,iii])
\end{Mexin}
\begin{Mexout}
[[1, a, i], [1, a, ii], [1, a, iii], [1, b, i], [1, b, ii],

   [1, b, iii], [2, a, i], [2, a, ii], [2, a, iii], [2, b, i],

   [2, b, ii], [2, b, iii], [3, a, i], [3, a, ii],

   [3, a, iii], [3, b, i], [3, b, ii], [3, b, iii]]
\end{Mexout}
\begin{Mexin}
permutations(3)
\end{Mexin}
\begin{Mexout}
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2],

   [3, 2, 1]]
\end{Mexout}
\begin{Mexin}
subwords([a,b,c,d])
\end{Mexin}
\begin{Mexout}
[[], [a], [b], [c], [d], [a, b], [a, c], [a, d], [b, c],

   [b, d], [c, d], [a, b, c], [a, b, d], [a, c, d], [b, c, d],

   [a, b, c, d]]
\end{Mexout}

\eng{Dyck words, as stated above, can be interpreted as balanced
  sequences of parentheses:}
\begin{Mexin}
map(dyckWords(4), dyckWords::toString)
\end{Mexin}
\begin{Mexout}
["(((())))", "((()()))", "((())())", "((()))()", "(()(()))",

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

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

%\eng{xxx Better, maybe more examples!}

\newpage

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