%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% $Id: CombinatorialClass.tex,v 1.1.1.4 2004/10/04 17:25:13 nthiery Exp $
% File:		lib/DOMAINS/CATEGORY/DOC/CombinatorialClass.tex
% Authors:	Nicolas M. Thiéry <nthiery@users.sourceforge.net>
%               Florent Hivert <florent.hivert@univ-mlv.fr>
% Purpose:	Documentation for the category Cat::CombinatorialClass
% Created:	Wed Sep  3 14:53:46 2003
% License:	LGPL
% Project:	MuPAD-Combinat, http://mupad-combinat.sf.net
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{Mhelppage}{CombinatorialClass}{Nicolas M. Thiéry, Florent Hivert}
  [ImplState=stable,TestState=stable,DocState=stable]
%\Mproofread{...}{...}{...}

\begin{MInfo}
  \eng{the category of combinatorial classes}
  \de{}
\end{MInfo}

\begin{MIntro}
  \eng{\Mthis{} represents the category of combinatorial classes that is the
  categories of sets that can be enumerated, counted\dots}
  \de{}
\end{MIntro}

\begin{MCatConst}
  \MCall{}
\end{MCatConst}

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

\begin{MDetails}
  \eng{A combinatorial class is a set of\ ``objects'' sharing a same
    combinatorial property, for example the set of binary trees, the set of
    integer partitions, \dots This has to be understood as a rough definition
    because there is no strict formalization of what is a combinatorial
    class.}
  
  \eng{Each object of a combinatorial class is supposed to have a\ ``size''
    which is most of the time an integer, for example the number of node of a
    tree (see \Mup{combinat::trees}), but can be anything else, for example
    the size of a vector of nonnegative integers (see
    \Mup{combinat::integerVectors}) is a pair of integers: its sum and its
    length.}
  
  \eng{The purpose of the category \Mthis{} is to ensure that all
    combinatorial classes share a common interface. \Mthis also provide
    default implementations when there is no better algorithm.  For example,
    if you don't known how to count a set of combinatorial ``objects'', count
    is done by expanding the list, which can be very inefficient.}
  
  \eng{To define a proper combinatorial class \Mex{cl}, the domain \Mex{cl}
    must at least define the methods \Mex{cl::isA}, and one of the following
    combinations of methods, the other are provided by defaults:
    \begin{itemize}
    \item \Mex{cl::list};
    \item \Mex{cl::generator};
    \item \Mex{cl::first} and \Mex{cl::Next};
    \item \Mex{cl::last} and \Mex{cl::previous};
    \item \Mex{cl::unrank}.
    \end{itemize}
    Note that these default implementations can be very inefficient in time or
    space compared to ad-hoc implementations.}
  
  \eng{In a near future we plan to write some class to manipulate other
    classes (for example a subclass of a class). To this end, it is very
    important that the functions \Mex{isA}, \Mex{list}, \Mex{generator} take
    the very same argument.}

\end{MDetails}

\begin{MDomBasEntries}
%%   \MDomEntry{type}
%%   \eng{The \mupad{} type of the object belonging to the class. Note that if \Mex{cl} is
%%   a combinatorial class it is sufficient to call \Mex{testtype(obj, cl)} to
%%   test the type of a object.}
%%   \de{}

  \MDomEntry{domtype}
  \eng{The \mupad{} \emph{domain} of the object belonging to the class. Since a
  combinatorial class can be a facade domain, it can be different from \Mslot{dom}.}
  \de{}

  \MDomEntry{interfaceCombinatorialClass}
  \eng{The standard common interface of a domain that belongs to \Mthis.
    This is not really needed any more. }
\end{MDomBasEntries}

\MBasMethods %----------------------------------------------------------------

\begin{MMethodDetails}{isA}
  \infoEng{test if an object is an element of the class.}
  \infoDe{}
  \call{\Mtype{object} x, \Mopt{, \Mtype{size} s, \Mtype{constraints} c}}
    
  \eng{Check if an object belongs to the combinatorial class. Moreover if
    optional \Mpar{s} or \Mpar{c} are given, it check if the object verify the
    constraints. An domains that belongs to \Mthis{} should define \Mslot{isA}
    rather that \Mslot{type} and \Mslot{testtype}. Hence, these two functions does
    not accept extra constraints and are provided by default by \Mthis. This
    methods is mandatory. Note that if the computation of membership to the
    class is too complicated or even infeasible, isA may return the \mupad{}
    value \Mup{UNKNOWN}. For the moment this answer is treated as \Mex{TRUE}.}
\end{MMethodDetails}

\begin{MMethodDetails}{size}
  \infoEng{size of an object.}
  \infoDe{}
  \call{\Mtype{object} x}
  \eng{Returns the size of an object of the class.}
\end{MMethodDetails}

\begin{MMethodDetails}{count}
  \infoEng{count the number of objects.}
  \infoDe{}
  \call{\Mopt{\Mtype{size} s, \Mtype{constraints} c}}
  \eng{Returns the number of objects of the class. If the class is infinite
    then \Mpar{s} must be given. In this case \Mslot{count} returns the number
    of objects of the class of the size \Mpar{s}. Moreover, if \Mpar{c} is
    given, returns the number of objects of the class of the size \Mpar{s}
    satisfying the extra constraints \Mpar{c}.}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of the objects}
  \call{\Mopt{\Mtype{size} s, \Mtype{constraints} c}}
  
  \eng{Returns the list of objects of the class. If the class is infinite then
    \Mpar{s} must be given. In this case \Mslot{count} returns the number of
    objects of the class of the size \Mpar{s}. Moreover, if \Mpar{c} is given,
    returns the list of objects of the class of the size \Mpar{s} satisfying
    the extra constraints \Mpar{c}.}
  
  \eng{If \Mex{cl} is a combinatorial class, the call \Mex{cl(size)} is a
    shortcut for \Mex{cl::list(size)}. Note that this shortcut should be
    reserved at the interactive level an not during programming.}
\end{MMethodDetails}

\begin{MMethodDetails}{generator}
  \infoEng{generator for the objects}
  \call{\Mopt{\Mtype{size} s, \Mtype{constraints} c}}
  \eng{Returns a generator for the objects of the class. If \Mpar{s} or
    \Mpar{c} is given, returns the a generator for the objects of the class of
    the size \Mpar{s} satisfying the extra constraints \Mpar{c}.}
  
  \eng{If to write a class \Mex{cl} you need a default implementation for
    \Mex{cl::generator}, you can use one of the following which are provided
    by \Mthis{}:
    \begin{itemize}
    \item \Mup[Cat,CombinatorialClass]{cl::generatorFromList} using
      \Mup[Cat,CombinatorialClass]{cl::list};
    \item \Mup[Cat,CombinatorialClass]{cl::generatorFromNext} using
      \Mup[Cat,CombinatorialClass]{cl::first} and \Mup[Cat,CombinatorialClass]{cl::Next};
    \item \Mup[Cat,CombinatorialClass]{cl::generatorFromPrevious} using
      \Mup[Cat,CombinatorialClass]{cl::last} and \Mup[Cat,CombinatorialClass]{cl::previous};
    \item \Mup[Cat,CombinatorialClass]{cl::generatorFromUnrank} using
      \Mup[Cat,CombinatorialClass]{cl::unrank};
    \end{itemize}}
\end{MMethodDetails}

\begin{MMethodDetails}{first}
  \infoEng{first objects}
  \call{\Mopt{\Mtype{size} s, \Mtype{constraints} c}}
  \eng{Returns the first object of the class. If \Mpar{s} or
    \Mpar{c} is given, returns the first object of the class of
    the size \Mpar{s} satisfying the extra constraints \Mpar{c}.}
\end{MMethodDetails}

\begin{MMethodDetails}{last}
  \infoEng{last object}
  \call{\Mopt{\Mtype{size} s, \Mtype{constraints} c}}
  \eng{Returns the last object of the class. If \Mpar{s} or
    \Mpar{c} is given, returns the last object of the class of
    the size \Mpar{s} satisfying the extra constraints \Mpar{c}.}
\end{MMethodDetails}

\begin{MMethodDetails}{Next}
  \infoEng{next object}
  \call{\Mtype{object} o, \Mopt{\Mtype{size} s, \Mtype{constraints} c}}
  \eng{Returns the next object of the class. If \Mpar{s} or
    \Mpar{c} is given, returns the next object of the class of
    the size \Mpar{s} satisfying the extra constraints \Mpar{c}.}
\end{MMethodDetails}

\begin{MMethodDetails}{previous}
  \infoEng{previous object}
  \call{\Mtype{object} o, \Mopt{\Mtype{size} s, \Mtype{constraints} c}}
  \eng{Returns the previous object of the class. If \Mpar{s} or
    \Mpar{c} is given, returns the previous object of the class of
    the size \Mpar{s} satisfying the extra constraints \Mpar{c}.}
\end{MMethodDetails}

\begin{MMethodDetails}{rank}
  \infoEng{rank object}
  \call{\Mtype{object} o, \Mopt{\Mtype{size} s, \Mtype{constraints} c}}
  \eng{Returns the rank of the object \Mpar{o} in the list of the object
    belonging to class. If \Mpar{s} or \Mpar{c} is given, returns the rank of
    the object \Mpar{o} in the list of the object of the class of the size
    \Mpar{s} satisfying the extra constraints \Mpar{c}.}
\end{MMethodDetails}

\begin{MMethodDetails}{unrank}
  \infoEng{unrank object}
  \call{\Mtype{number} n, \Mopt{\Mtype{size} s, \Mtype{constraints} c}}
  \eng{Returns the \Mpar{n}-th object of the class. If \Mpar{s} or \Mpar{c} is
    given, returns the \Mpar{n}-th object of the class of the size \Mpar{s}
    satisfying the extra constraints \Mpar{c}.}
\end{MMethodDetails}

\begin{MMethodDetails}{random}
  \infoEng{random object}
  \call{\Mopt{\Mtype{size} s, \Mtype{constraints} c}}
  \eng{Returns a random object of the class. If \Mpar{s} or \Mpar{c} is
    given, returns a random object of the class of the size \Mpar{s}
    satisfying the extra constraints \Mpar{c}.}
\end{MMethodDetails}

\begin{MMethodDetails}{_less}
  \infoEng{comparison of two objects}
  \call{\Mopt{\Mtype{object} o1, \Mtype{object} o2}}
  \eng{Where it makes sense, compare the object \Mpar{o1} and \Mpar{o2} and
  returns true if \Mpar{o1} is smaller than \Mpar{o2}.}
\end{MMethodDetails}

\begin{MMethodDetails}{generatingSeries}
  \infoEng{the generating series of the class.}
  \infoDe{}
  \call{\Mopt{\Mtype{variable} z}}
  \eng{The generating series of a class $C$ is defined as
    $$
    f_C(z) := \sum_{x \in C} z^{\operatorname{size}(x)}
                = \sum_n \#\{\text{objects of $C$ of size $n$}\}\ z^n\,.
    $$
    Thus the coefficient of $x^n$ in the generating series $f_C(z)$ is the
    number of object of size $n$. When known \Mslot{generatingSeries} return an
    expression for the generating series. 
  }
\end{MMethodDetails}

\MTechMethods %----------------------------------------------------------------
\begin{MDetails}
  \eng{To help the writing of combinatorial classes, the following methods are
    provided. They are not supposed to be called directly, they are here
    rather to provide default implementations by using other methods.
    \Mwarn{Note that these default implementations can be very inefficient in
      time or space compared to ad-hoc implementations.}}
\end{MDetails}

\begin{MMethodDetails}{countFromGenerator}
  \infoEng{count the number of objects using generation.}
  \infoDe{}
  \call{\Mopt{\Mtype{size} s, \Mtype{constraints} c}}
  
  \eng{Returns the number of objects of the class. The counting is done by
    generating all the objects step by step.
    \Mwarn{This is the default implementation for the count methods if nothing is
      provided.}}
\end{MMethodDetails}
  
\begin{MMethodDetails}{listFromGenerator}
  \infoEng{list the number of objects using generation.}
  \infoDe{}
  \call{\Mopt{\Mtype{size} s, \Mtype{constraints} c}}
  
  \eng{Returns the list of objects of the class. This is done by generating
    all the objects step by step, using a size-doubling arrays to avoid
    reallocating the list at each step.
    \Mwarn{This is the default implementation for the list methods if nothing is
      provided.} }
\end{MMethodDetails}

%----------------------------------------------------------------

\begin{MDetails}
  \eng{The following methods are defaults implementations for \Mslot{generator}.
    The categories \Mthis{} try in the following order to use these
    implementations when the necessary functions are defined:
    \begin{itemize}
    \item \Mslot{generatorFromNext} if \Mslot{first} and \Mslot{Next} are defined;
    \item \Mslot{generatorFromPrevious} if \Mslot{last} and \Mslot{previous} are
      defined;
    \item \Mslot{generatorFromUnrank} if \Mslot{Unrank} is defined;
    \item \Mslot{generatorFromList} if \Mslot{list} is defined
    \end{itemize}}
  \eng{If no implementation is possible because the necessary methods are not
    provided, an error is raised at the first call of \Mslot{generator} or
    \Mslot{list}.}
\end{MDetails}
    
\begin{MMethodDetails}{generatorFromNext}
  \infoEng{generator for the objects using \Mslot{first} and \Mslot{Next}}
  \call{\Mopt{\Mtype{size} s, \Mtype{constraints} c}}
  
  \eng{Returns a generator for the objects of the class. This is done by
    calling \Mslot{Next} at each step, which is most of the time a relatively
    good implementations with respect to time and space.

    \Mwarn{This is the default implementation for the generator methods if
      \Mslot{first} and \Mslot{Next} are provided.}}
\end{MMethodDetails}

\begin{MMethodDetails}{generatorFromPrevious}
  \infoEng{generator for the objects using \Mslot{last} and \Mslot{previous}}
  \call{\Mopt{\Mtype{size} s, \Mtype{constraints} c}}
  
  \eng{Returns a generator for the objects of the class. This is done by
    calling \Mslot{previous} at each step, which is most of the time a relatively
    good implementations with respect to time and space.}
\end{MMethodDetails}
    
\begin{MMethodDetails}{generatorFromUnrank}
  \infoEng{generator for the objects using \Mslot{unrank}}
  \call{\Mopt{\Mtype{size} s, \Mtype{constraints} c}}
  
  \eng{Returns a generator for the objects of the class. This is done by
    calling \Mslot{unrank} at each step, which is most of the time a relatively
    good implementations with respect to time and space.}
\end{MMethodDetails}
    
\begin{MMethodDetails}{generatorFromList}
  \infoEng{generator for the objects using \Mslot{list}}
  \call{\Mopt{\Mtype{size} s, \Mtype{constraints} c}}
  
  \eng{Returns a generator for the objects of the class. This is done by
    expanding the list when the generator is constructed.
    \Mwarn{This is the fallback implementation of generator if noting better
      is possible. This is very inefficient with respect to memory space.}}
\end{MMethodDetails}

%----------------------------------------------------------------

\begin{MExample}{combClass}
  \eng{Suppose that you want to define the combinatorial class of the binary
    vectors. The size is the length of the vector. It is easy to write a
    \Mslot{Next} function, by thinking that a vector is a binary expansion of a
    number. This is done by searching the first $0$ and replacing the initial
    sequence $11\dots10$ by $00\dots01$. Here is a way to do this:}
  \begin{Mexin}
    nextBinExp := proc(lst)
        local pos;
    begin
       if (pos := contains(lst, 0)) <> 0 then 
           [ 0$(pos-1), 1, op(lst, pos+1..nops(lst))]
       else FAIL
       end_if;  
    end:
    nextBinExp([1, 1, 0, 1, 0, 1, 1, 0]);
  \end{Mexin}
  \begin{Mexout}
                   [0, 0, 1, 1, 0, 1, 1, 0]
  \end{Mexout}
  \eng{Here is the way to use that to build a combinatorial class. We
    have to define \Mslot{isA} for the type checking and
    \Mslot{first}, \Mslot{Next} for generation :}
  \begin{Mexin}
domain zeroOneVectors 
    inherits Dom::BaseDomain;
    category Cat::CombinatorialClass;
    axiom    Ax::systemRep;
    
    isA := // Type checking.
    proc(obj         : Type::AnyType,
        size = FAIL : Type::Union(Type::NonNegInt, DOM_FAIL)) : DOM_BOOL
    begin
        if domtype(obj) <> DOM_LIST then return(FALSE); end_if;
        if {op(obj)} minus {0,1} <> {} then return(FALSE); end_if;
        if args(0) = 1 then return(TRUE);
        else
            bool(nops(obj) = size);
        end_if;
    end_proc;

    size  := proc(v : dom) : Type::NonNegInt begin nops(v); end_proc;
                
    first := proc(size : Type::NonNegInt) : dom
             begin
                 [ 0 $ size ];
             end_proc;

    Next := proc(lst : dom) : Type::Union(DOM_FAIL, dom)
                local pos;
            begin
                if (pos := contains(lst, 0)) <> 0 then 
                    [ 0$(pos-1), 1, op(lst, pos+1..nops(lst))]
                else FAIL
                end_if;  
            end_proc;
end_domain:
  \end{Mexin}
  \eng{The type Checking is working:}
  \begin{Mexin}
testtype([1, 0, 1], zeroOneVectors);
testtype([1, 0, 2], zeroOneVectors)
  \end{Mexin}
  \begin{Mexout}
                             TRUE

                             FALSE
  \end{Mexout}
  \eng{The methods \Mslot{list} is provided by \Mthis{}}
  \begin{Mexin}
zeroOneVectors::list(3)
  \end{Mexin}
  \begin{Mexout}
[[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 0, 1],

   [1, 0, 1], [0, 1, 1], [1, 1, 1]]
  \end{Mexout}
  \eng{together with the method \Mslot{generator}:}
  \begin{Mexin}
(g := zeroOneVectors::generator(2); 
g(), g(), g(), g(), g())
  \end{Mexin}
  \begin{Mexout}
             [0, 0], [1, 0], [0, 1], [1, 1], FAIL
  \end{Mexout}
  \eng{The following useful shortcut is also defined}
  \begin{Mexin}
zeroOneVectors(3)
  \end{Mexin}
  \begin{Mexout}
[[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 0, 1],

   [1, 0, 1], [0, 1, 1], [1, 1, 1]]
  \end{Mexout}
  \eng{A default implementation is provided for the \Mslot{count} method:}
  \begin{Mexin}
zeroOneVectors::count(4)
  \end{Mexin}
  \begin{Mexout}
                              16
  \end{Mexout}
  \eng{However, it is very slow, since it simply generates all the
    elements, and count them:}
  \begin{Mvin}{test=false}
zeroOneVectors::count(10);
time(zeroOneVectors::count(10))
  \end{Mvin}
  \begin{Mvout}{test=false}
                             1024

                             240
  \end{Mvout}
  \eng{Whenever possible, it is better to implement the \Mslot{count}
    method:}
    \begin{Mvin}{test=false}
zeroOneVectors::count := i -> 2^i:
zeroOneVectors::count(10);
time(zeroOneVectors::count(10))
  \end{Mvin}
  \begin{Mvout}{test=false}
                             1024

                               0
  \end{Mvout}

\end{MExample}

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

\end{Mhelppage}
