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

\begin{MInfo}
  \eng{subwords of a word}
\end{MInfo}

\MDeclareOption{\Repeat}{Repeat}

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

\MKeywords{combinatorics,words}

\begin{MDetails}
  \eng{A subword of a word $w$ is a word obtained by deleting the
    letters at some of the positions in $w$ (see also
    \Mup{combinat::words}). A subword is generated as many times
    as it appears in the word.}% 
  \eng{Sometimes, a letter in the word $w$ can be repeated several 
       times in the subword, even it only appears once in $w$.
       This is done with the option \Repeat.}
\end{MDetails}

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

\MRelatedDomains{combinat::words}

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

\begin{MMethodDetails}{count}
  \infoEng{number of subwords of a word}
  \call{\Mtype{word} A}
  \eng{Returns the number of subwords of a word.}
  \call{\Mtype{word} A, \Mtype{nonnegative integer} k \Mopt{, Repeat}}
  \eng{Returns the number of subwords of length $k$ of a word, with
  optional repetition of letters.}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of the subwords of a word}
  \call{\Mtype{word} A}
  \eng{Returns the list of the subwords of a word.}
  \call{\Mtype{word} A, \Mtype{nonnegative integer} k \Mopt{, Repeat}}
  \eng{Returns the list of the subwords of length $k$ of a word, with
  optional repetition of letters.}
 \end{MMethodDetails}

\begin{MMethodDetails}{generator}
  \infoEng{generator for subwords of a word}
  \call{\Mtype{word} A}
  \eng{Returns a generator for subwords of a word.}
  \call{\Mtype{word} A, \Mtype{nonnegative integer} k \Mopt{, Repeat}}
  \eng{Returns a generator for subwords of length $k$ of a word, with
  optional repetition of letters.}
\end{MMethodDetails}

\begin{MMethodDetails}{first}
  \infoEng{first subword of a word} 
  \call{\Mtype{word} A}
  \eng{Returns the first subword of a word.} 
  \call{\Mtype{word} A, \Mtype{nonnegative integer} k \Mopt{, Repeat}}
  \eng{Returns the first subword of length $k$ of a word, with
  optional repetition of letters.}
\end{MMethodDetails}

\begin{MMethodDetails}{last}
  \infoEng{last subword of a word}     
  \call{\Mtype{word} A}
  \eng{Returns the last subword of a word.}       
  \call{\Mtype{word} A, \Mtype{nonnegative integer} k \Mopt{, Repeat}}
  \eng{Returns the first subword of length $k$ of a word, with
  optional repetition of letters.}
\end{MMethodDetails}


\begin{MExample}{word-basic}
  \eng{There are $8$ subwords of the word \Mex{[a, c, b]}:}
  \begin{Mexin}
combinat::subwords::count([a, c, b])
  \end{Mexin}
  \begin{Mexout}
                               8
  \end{Mexout}
  \eng{Here is the list:}
  \begin{Mexin}
combinat::subwords::list([a, b, c])
  \end{Mexin}
  \begin{Mexout}
    [[], [a], [b], [c], [a, b], [a, c], [b, c], [a, b, c]]
  \end{Mexout}
  \eng{To compute the subwords of a given length:}
  \begin{Mexin}
combinat::subwords::count([a, c, b, b, c], 3);
combinat::subwords::list([a, c, b, b, c], 3)
  \end{Mexin}
  \begin{Mexout}
                              10

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

   [a, b, c], [c, b, b], [c, b, c], [c, b, c], [b, b, c]]
  \end{Mexout}
  \eng{\Mwarn{Note that the word \Mex{[a, c, b]} is repeated twice.}}

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

   [c, b, c], [c, b, c], [b, b, c], FAIL
  \end{Mexout}

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

                            [a, b]

                            [a, a]

                            [b, b]

                            [b, a]

                            [b, a]
  \end{Mexout}
  
  \eng{The ``first'' and ``last'' subwords of length $k$, also called
    left and right factors are computed in this example:}%
  \begin{Mexin}
combinat::subwords::first([a, b, b, a, d, b, a], 3);
combinat::subwords::last([a, b, b, a, d, b, a], 3);
  \end{Mexin}
  \begin{Mexout}
                           [a, b, b]
 
                           [d, b, a]
  \end{Mexout}
\end{MExample}


\begin{MExample}{repeat-word}
  \eng{To list the non-decreasing words of \Mex{[a, b, d]}, you just have
  to list the subwords of \Mex{[a, b, d]} with repetitions:}
  \begin{Mexin}
combinat::subwords::list([a, b, d], 3, Repeat);
  \end{Mexin}
  \begin{Mexout}
[[a, a, a], [a, a, b], [a, a, d], [a, b, b], [a, b, d],

   [a, d, d], [b, b, b], [b, b, d], [b, d, d], [d, d, d]]
  \end{Mexout}
  \eng{It also works for an input word with repeated letters:}
  \begin{Mexin}
combinat::subwords::list([a, b, b], 3, Repeat);
  \end{Mexin}
  \begin{Mexout}
[[a, a, a], [a, a, b], [a, a, b], [a, b, b], [a, b, b],

   [a, b, b], [b, b, b], [b, b, b], [b, b, b], [b, b, b]]
  \end{Mexout}
  \eng{And also with generators:}
  \begin{Mexin}
g := combinat::subwords::generator([a, b, b], 3, Repeat):
g(), g();
g(), g(), g(), g(), g(), g(), g(), g(), g();
  \end{Mexin}
  \begin{Mexout}
                     [a, a, a], [a, a, b]

[a, a, b], [a, b, b], [a, b, b], [a, b, b], [b, b, b],

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

\MSuperDomain{Dom::BaseDomain}

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

\end{Mhelppage}
