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

\begin{MInfo}
  \eng{subsets of a set}
\end{MInfo}

\begin{MIntro}
  \eng{The library \Mthis{} provides functions for counting,
    generating, and manipulating the subsets of a set.}
\end{MIntro}

\MKeywords{combinatorics,subset,powerset}

%\begin{MDetails}
%\end{MDetails}

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

\begin{MDomEntries}
  \MDomEntry{domtype}
     \eng{The \mupad\ domain used to represent subsets:
       \Mup{DOM_SET}}
\end{MDomEntries}

\begin{MMethodDetails}{count}
  \infoEng{number of subsets}
  \call{\Mtype{set} s}
  \eng{Returns the number of subsets of \Mpar{s}.}
  \call{\Mtype{nonnegative integer} n}
  \eng{Returns the number of subsets of \Mmath{{1, 2, ..., n}}{\{1, 2, \ldots,
      n\}}.}

  \call{\Mtype{set} s, \Mtype{nonnegative integer} k}
  \eng{Returns the number of subsets of \Mpar{s} of size \Mpar{k}.}
  \call{\Mtype{nonnegative integer} n, \Mtype{nonnegative integer} k}
  \eng{Returns the number of subsets of \Mmath{{1, 2, ..., n}}{\{1, 2, \ldots,
      n\}} of size \Mpar{k}.}
\end{MMethodDetails}

\begin{MMethodDetails}{generator}
  \infoEng{generator for subsets}
  \call{\Mtype{set} s}
  \eng{Returns a generator for the subsets of \Mpar{s}.}
  \call{\Mtype{nonnegative integer} n}
  \eng{Returns a generator for the subsets of \Mmath{{1, 2, ..., n}}{\{1, 2, \ldots,
      n\}}.}

  \call{\Mtype{set} s, \Mtype{nonnegative integer} k}
  \eng{Returns a generator for the subsets of \Mpar{s} of size \Mpar{k}.}
  \call{\Mtype{nonnegative integer} n, \Mtype{nonnegative integer} k}
  \eng{Returns  a generator for the subsets of \Mmath{{1, 2, ..., n}}{\{1, 2, \ldots,
      n\}} of size \Mpar{k}.}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of the subsets}
  \call{\Mtype{set} s}
  \eng{Returns the list of the subsets of \Mpar{s}.}
  \call{\Mtype{nonnegative integer} n}
  \eng{Returns the list of the subsets of \Mmath{{1, 2, ..., n}}{\{1, 2, \ldots,
      n\}}.}

  \call{\Mtype{set} s, \Mtype{nonnegative integer} k}
  \eng{Returns the list of the subsets of \Mpar{s} of size \Mpar{k}.}
  \call{\Mtype{nonnegative integer} n, \Mtype{nonnegative integer} k}
  \eng{Returns  the list of the subsets of \Mmath{{1, 2, ..., n}}{\{1, 2, \ldots,
      n\}} of size \Mpar{k}.}
\end{MMethodDetails}

\begin{MMethodDetails}{first}
  \infoEng{first subset}
  \call{\Mtype{set} s}
  \eng{Returns the first subset of \Mpar{s}.}
  \call{\Mtype{nonnegative integer} n}
  \eng{Returns the first subset of \Mmath{{1, 2, ..., n}}{\{1, 2, \ldots,
      n\}}.}

  \call{\Mtype{set} s, \Mtype{nonnegative integer} k}
  \eng{Returns the first subset of \Mpar{s} of size \Mpar{k}, or FAIL
    if there is none.}
  \call{\Mtype{nonnegative integer} n, \Mtype{nonnegative integer} k}
  \eng{Returns the first subset of \Mmath{{1, 2, ..., n}}{\{1, 2, \ldots,
      n\}} of size \Mpar{k}, or FAIL if there is none.}
\end{MMethodDetails}
    
\begin{MMethodDetails}{last}
  \infoEng{last subset}
  \call{\Mtype{set} s}
  \eng{Returns the last subset of \Mpar{s}.}
  \call{\Mtype{nonnegative integer} n}
  \eng{Returns the last subset of \Mmath{{1, 2, ..., n}}{\{1, 2, \ldots,
      n\}}.}

  \call{\Mtype{set} s, \Mtype{nonnegative integer} k}
  \eng{Returns the last subset of \Mpar{s} of size \Mpar{k}.}
  \call{\Mtype{nonnegative integer} n, \Mtype{nonnegative integer} k}
  \eng{Returns the last subset of \Mmath{{1, 2, ..., n}}{\{1, 2, \ldots,
      n\}} of size \Mpar{k}.}
\end{MMethodDetails}

\begin{MExample}{ex-basic}
  \eng{There are $8$ subsets of \Mex{{1,2,3}}:}
  \begin{Mexin}
combinat::subsets::count(3);
combinat::subsets::count({1,2,3})
  \end{Mexin}
  \begin{Mexout}
                               8

                               8
  \end{Mexout}

  \eng{There are $15$ subsets of size $2$ in a set of size $6$:}
  \begin{Mexin}
combinat::subsets::count(6,2);
combinat::subsets::count({a,b,c,d,e,f},2)
  \end{Mexin}
  \begin{Mexout}
                              15

                              15
  \end{Mexout}

  \eng{Here is the list of the subsets of \Mex{{a,b,c,d,e}} of size $3$:}
  \begin{Mexin}
combinat::subsets::list({a,b,c,d,e}, 3)
  \end{Mexin}
  \begin{Mexout}
[{a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e},

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

  \eng{You can use the functions \Mex{combinat::subsets::first} and
    \Mex{combinat::subsets::last} to get the ``first'' and ``last''
    subset of a set:}
  \begin{Mexin}
combinat::subsets::first(4);
combinat::subsets::first({1,2,3,4});
combinat::subsets::first(4,2);
combinat::subsets::first({1,2,3,4},2);
combinat::subsets::last(4);
combinat::subsets::last({1,2,3,4});
combinat::subsets::last(4,2);
combinat::subsets::last({1,2,3,4},2);
  \end{Mexin}
  \begin{Mexout}
                              {}

                              {}

                            {1, 2}

                            {1, 2}

                         {1, 2, 3, 4}

                         {1, 2, 3, 4}

                            {3, 4}
 
                            {3, 4}
  \end{Mexout}
  \eng{The specified size for the subsets can exceed the size of the
    set itself:}
  \begin{Mexin}
combinat::subsets::count({1,2,3}, 4);
combinat::subsets::list({1,2,3}, 4);
combinat::subsets::first({1,2,3}, 4);
  \end{Mexin}
  \begin{Mexout}
                               0

                              []

                             FAIL
  \end{Mexout}

\eng{When you want to run through the subsets of a set, you can
  generate them one by one to save memory:}
\begin{Mexin}
g := combinat::subsets::generator(3):
g(); g(); g(); g(); g(); g()
\end{Mexin}
\begin{Mexout}
                              {}
 
                              {1}
 
                              {2}
 
                              {3}
 
                            {1, 2}
 
                            {1, 3}
\end{Mexout}

\eng{Typically, this would be used as follows:}
\begin{Mexin}
g := combinat::subsets::generator(4,2):
while (p := g()) <> FAIL do print(p): end:
\end{Mexin}
\begin{Mexout}
                            {1, 2}
 
                            {1, 3}
 
                            {1, 4}
 
                            {2, 3}
 
                            {2, 4}
 
                            {3, 4}
\end{Mexout}
\end{MExample}

%\begin{MBackground}
%\end{MBackground}

\begin{MChanges}
  \version{2.5}%
  \eng[New library]{\Mthis{} is a new library}%
  \eng[Deprecates combinat::choose and combinat::powerset]{This
    library replaces and extends the functionalities of
    \Mup{combinat::choose} and \Mup{combinat::powerset}. The later are
    temporarily retained for backward compatibility; however, their
    use is strongly deprecated and raises a warning (this warning can
    be disabled with \Mupc{combinat::warnDeprecated}{FALSE}). Please
    use \Mup{combinat::subsets::list} instead. }
\end{MChanges}

\MSuperDomain{Dom::BaseDomain}

\begin{MAxioms}
  \Mup{Ax::systemRep}
\end{MAxioms}


\end{Mhelppage}

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