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

\begin{MInfo}
  \eng{cartesian products}
\end{MInfo}

\begin{MIntro}
  \eng{The library \Mthis{} provides functions for counting and
    generating elements of cartesian products of sets.}
\end{MIntro}

\MKeywords{combinatorics,cartesian product}

\begin{MDetails}
  \eng{Let \Mmath{s1, s2, ..., sk}{s1,s2,\dots,sk} be \Mmath{k}{k} sets.
    The cartesian product \Mmath{s1 x s2 x ... x sk}{s1\times
      s2\times\dots\times sk} of \Mmath{s1,s2,...,sk}{s1,s2,\dots,sk} is the
    set of all \Mmath{k}{k}-tuples \Mmath{[x1,x2,...,xk]}{[x1,x2,\dots,xk]}
    with \Mmath{xi}{xi} in \Mmath{si}{si} for each \Mmath{i}{i}, \Mmath{1<=i<=k}{1\leq
      i \leq k}.}
  
  \eng{Each set \Mmath{si}{si} can be represented either by a set (\Mup{DOM_SET}),
    a list (\Mup{DOM_LIST}), or an integer (which represents the set
    \Mmath{{1,2,...,n}}{\{1,2,\ldots,n\}}).}
\end{MDetails}

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

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

\begin{MMethodDetails}{isA}
  \infoEng{test if an object is a cartesian product}
  \call{\Mtype{any type} cp\Mopt{, \Mtype{set or list or nonnegative integer} s1, \ldots, 
                                   \Mtype{set or list or nonnegative integer} sk}}
  \eng{Returns whether the object \Mpar{cp} is an element of a cartesian product.}
  \eng{If optional arguments are present, returns whether \Mpar{cp} is a
   an element of the cartesian product of \Mpar{s1}, \ldots, \Mpar{sk}.}
\end{MMethodDetails}

\begin{MMethodDetails}{count}
  \infoEng{number of elements of a cartesian product}%
  \call{\Mopt{\Mtype{set} s1} \Mopt{, \Mtype{set} s2}
    \Mopt{, \dots, \Mtype{set} sk}}%
  \eng{Returns the number of elements of the cartesian product
    \Mmath{s1 x s2 x ... x sk}{s1\times s2\times\dots\times sk}.}
\end{MMethodDetails}

\begin{MMethodDetails}{generator}
  \infoEng{generator for the elements of a cartesian product}%
  \call{\Mopt{\Mtype{set} s1} \Mopt{, \Mtype{set} s2}
    \Mopt{, \dots, \Mtype{set} sk}}%
  \eng{Returns a generator for the elements of the cartesian product
    \Mmath{s1 x s2 x ... x sk}{s1\times s2\times\dots\times sk}.}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of the elements of a cartesian product}%
  \call{\Mopt{\Mtype{set} s1} \Mopt{, \Mtype{set} s2}
    \Mopt{, \dots, \Mtype{set} sk}}%
  \eng{Returns the list of the elements of the cartesian product
    \Mmath{s1 x s2 x ... x sk}{s1\times s2\times\dots\times sk}.}
\end{MMethodDetails}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Examples
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{MExample}{car-pro-isA}
  \eng{In this example we show how to check whether we have an element
       of a cartesian product of some sets. The sets can be represented 
       either by a list, a set or a non negative integer.}
  \begin{Mexin}
combinat::cartesianProduct::isA([2, 3, 4], {1, 2}, [a, 3], 7);
combinat::cartesianProduct::isA([2, 3, 4, d], 2, 3, 4, {a, d});
combinat::cartesianProduct::isA([2, 3, 4, d], 2, 1, 4, {a, d});
combinat::cartesianProduct::isA([2, 3, 4, d], 2, 3);
  \end{Mexin}
  \begin{Mexout}
                             TRUE

                             TRUE

                             FALSE

                             FALSE
  \end{Mexout}
  \eng{If no optional argument is provided (i.e. the sets), the function tests
       whether an object makes sense as an element of a cartesian product.}
  \begin{Mexin}
combinat::cartesianProduct::isA([2, 3, 4, d]);
combinat::cartesianProduct::isA([ ]);
combinat::cartesianProduct::isA(a);
  \end{Mexin}
  \begin{Mexout}
                             TRUE

                             TRUE

                             FALSE
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-basic}
  \eng{There are $12$ elements in the cartesian product of
    the sets \Mex{\{1,2,3\}} and \Mex{\{a,b,c,d\}}:}
  \begin{Mexin}
combinat::cartesianProduct::count({1,2,3},{a,b,c,d});
  \end{Mexin}
  \begin{Mexout}
                              12
  \end{Mexout}

  \eng{Here is the list:}
  \begin{Mexin}
combinat::cartesianProduct::list({1,2,3},{a,b,c,d});
  \end{Mexin}
  \begin{Mexout}
[[1, a], [1, b], [1, c], [1, d], [2, a], [2, b], [2, c],

   [2, d], [3, a], [3, b], [3, c], [3, d]]
  \end{Mexout}
  
  \eng{When you want to run through the elements of a cartesian
    product you can generate them one by one to save memory:}
  \begin{Mexin}
g := combinat::cartesianProduct::generator({1,2},{a,b}):
g(); g(); g(); g(); g()
  \end{Mexin}
  \begin{Mexout}
                            [1, a]

                            [1, b]

                            [2, a]

                            [2, b]

                             FAIL
  \end{Mexout}

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

                            [1, b]

                            [2, a]

                            [2, b]
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-variations}
  \eng{Each input set can be represented by a set, a list, or a number:}
  \begin{Mexin}
combinat::cartesianProduct::list({a,b},[x,y],2);
  \end{Mexin}
  \begin{Mexout}
[[a, x, 1], [a, x, 2], [a, y, 1], [a, y, 2], [b, x, 1],

   [b, x, 2], [b, y, 1], [b, y, 2]]
  \end{Mexout}

  \eng{The empty cartesian product has one element:}
  \begin{Mexin}
combinat::cartesianProduct::list();
  \end{Mexin}
  \begin{Mexout}
                             [[]]
  \end{Mexout}
  
  \eng{When any one of the sets is empty, the cartesian product is
    also empty:}
  \begin{Mexin}
combinat::cartesianProduct::list(2,0);
  \end{Mexin}
  \begin{Mexout}
                              []
  \end{Mexout}

  \eng{The cartesian product is not commutative:}
  \begin{Mexin}
combinat::cartesianProduct::list({Diamondsuit},2);
combinat::cartesianProduct::list(2,{Diamondsuit})
  \end{Mexin}
  \begin{Mexout}
             [[Diamondsuit, 1], [Diamondsuit, 2]]

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

\begin{MExample}{ex-applications}
  \eng{Which cards exist, if you have the following suits and numbers
    available?}
  \begin{Mexin}
combinat::cartesianProduct::list(
          {Diamondsuit,Heartsuit,Spadesuit,Clubsuit},
          {7,8,9,10})
  \end{Mexin}
  \begin{Mexout}
[[Diamondsuit, 7], [Diamondsuit, 8], [Diamondsuit, 9],
 
   [Diamondsuit, 10], [Heartsuit, 7], [Heartsuit, 8],
 
   [Heartsuit, 9], [Heartsuit, 10], [Spadesuit, 7],
 
   [Spadesuit, 8], [Spadesuit, 9], [Spadesuit, 10],
 
   [Clubsuit, 7], [Clubsuit, 8], [Clubsuit, 9], [Clubsuit, 10]]
  \end{Mexout}
\end{MExample}

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