% $Id: words.tex,v 1.1.1.7 2005/01/26 13:42:24 nthiery Exp $
\begin{Mhelppage}{words}{F.~Hivert and N.~Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
\Mproofread{teresa}{10/2003}{proofread}

\begin{MInfo}
  \eng{words}
\end{MInfo}

\begin{MIntro}
  \eng{The library \Mthis{} provides functions for counting,
    generating, and manipulating words.}
\end{MIntro}

\MKeywords{combinatorics,words}

\begin{MDetails}
  \eng{A \emph{word} of length $k$ over the \emph{alphabet} $A$ is a
    list of $k$ elements of $A$. The alphabet $A$ can be represented
    in \mupad\ by a set (\Mup{DOM_SET}) or a list (\Mup{DOM_LIST}). A
    nonnegative integer $n$ can be used as a shortcut for the alphabet
    \Mex{[1,2,\Mseq{},n]}. The order between the letters is specified
    by the order of the operands in $A$.}
\end{MDetails}

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

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

\begin{MMethodDetails}{isA}
  \infoEng{check if an object is a word}
  \call{\Mtype{word} w, \Mopt{\Mtype{alphabet} A, \Mtype{size} k}}
  \call{\Mtype{word} w, \Mopt{\Mtype{nonnegative integer} n, \Mtype{size} k}}
    
  \eng{Returns true if \Mpar{w} is a word. If the alphabet or the size is
    given check also if \Mpar{w} is of length \Mpar{k} on the alphabet
    \Mpar{A} or \Mex{[1,2,\Mseq{},n]}.}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of the words}
  \call{\Mtype{alphabet} A, \Mtype{nonnegative integer} k}
  \call{\Mtype{nonnegative integer} n, \Mtype{nonnegative integer} k}%
  \eng{Returns the list of the words of length \Mpar{k} on the
    alphabet \Mpar{A} or \Mex{[1,2,\Mseq{},n]}.}
\end{MMethodDetails}

\begin{MMethodDetails}{generator}
  \infoEng{generator for words}%
  \call{\Mtype{alphabet} A, \Mtype{nonnegative integer} k}%
  \call{\Mtype{nonnegative integer} n, \Mtype{nonnegative integer} k}%
  \eng{Returns a generator for the words of length \Mpar{k} on the
    alphabet \Mpar{A} or \Mex{[1,2,\Mseq{},n]}.}
\end{MMethodDetails}

\begin{MMethodDetails}{alphabetToOrder}
  \infoEng{ordering function of an alphabet}%
  \call{\Mtype{alphabet} A}%
  \eng{Returns the ordering function of the alphabet \Mpar{A}. Such a
    function takes two element \Mpar{x} and \Mpar{y} of \Mpar{A} and
    returns \Mup{TRUE} if \Mpar{x} occurs before \Mpar{y} in \Mpar{A}.}
\end{MMethodDetails}

\begin{MMethodDetails}{standard}
  \infoEng{standard permutation of a word}
  \call{\Mtype{word} w}%
  \call{\Mtype{word} w, \Mtype{alphabet} A}%
  \call{\Mtype{word} w, \Mtype{ordering} o}%
  \eng{Returns the standard permutation of the word \Mpar{w} on the
    ordered alphabet \Mpar{A}. It is defined as the permutation with
    exactly the same inversions than \Mpar{w} (see
    \Mup{combinat::permutations}). By default, the letters are ordered
    using \Mup{<}. A custom ordering can be specified by providing an
    alphabet \Mpar{A}, or an ordering function \Mpar{o} that returns
    \Mup{TRUE} if its first argument is smaller than its second one.}
  % make this more precise
\end{MMethodDetails}

\MethodSection{Evaluations of words}

\begin{MDetails}
  \eng{The \emph{evaluation} of a word \Mex{w} encodes the number of
    occurrences of each letter of \Mex{w}.}
  
  \eng{In general, the evaluation may be represented as a table, the
    evaluation of \Mex{[1,1,1,2,1,4,4]} being
    \Mex{table(1=4, 2=1, 4=2)}, or as a sorted associative list
    \Mex{[[1,4], [2,1], [4,2]]}.}
  
  \eng{When an ordered alphabet is specified, the evaluation can be
    represented as an integer vector \Mex{c} such that \Mex{c[i]} is
    the number of occurrences of the \Mex{i}-th letter of the alphabet
    in \Mex{w}.  With the above word and the alphabet \Mex{[2,1,4]},
    we get the evaluation \Mex{[1,4,2]}. In the special case where
    \Mex{w} is a vector with positive integer entries, the alphabet
    \Mex{[1,\dots,max(w)]} is used by default. This yields
    \Mex{[4,1,0,2]} with our example.}
  
  \eng{If the underlying letters are irrelevant, the evaluation may be
    represented as a partition such as \Mex{[4,2,1]} in the example
    above.}
\end{MDetails}

\begin{MMethodDetails}{evaluation}
  \infoEng{evaluation of a word, as an integer vector}
  \call{\Mtype{word} w\Mopt{, \Mtype{alphabet} a}}%
  \eng{Returns the evaluation of \Mpar{w} as an integer vector.}
\end{MMethodDetails}

\begin{MMethodDetails}{evaluationPartition}[ImplState=stable,TestState=beta,DocState=beta]
  \infoEng{evaluation of a word, as a partition}
  \call{\Mtype{word} w}%
  \eng{Returns the evaluation of \Mpar{w} as a partition.}
\end{MMethodDetails}

\begin{MMethodDetails}{evaluationTable}[ImplState=stable,TestState=stable,DocState=beta]
  \infoEng{evaluation of a word, as a table}
  \call{\Mtype{word} w}%
  \eng{Returns the evaluation of \Mpar{w} as a table.}
\end{MMethodDetails}

\begin{MMethodDetails}{evaluationSparse}[ImplState=stable,TestState=stable,DocState=beta]
  \infoEng{evaluation of a word, as a table}
  \call{\Mtype{word} w}%
  \eng{Returns the evaluation of \Mpar{w} as a sorted associative list.}
  \eng{The letters are sorted with \Mup{sort}.}
  \eng{This method is likely to be renamed.}
  % In GAP, this is the Collected command, Chapter 21.20 of the ref. man.
\end{MMethodDetails}

\begin{MMethodDetails}{fromStandardAndEvaluation}[ImplState=stable,TestState=stable,DocState=alpha]
  \infoEng{word from its standard permutations and evaluation}
  \call{\Mtype{standard permutation} p, \Mtype{evaluation} e\Mopt{,
  \Mtype{alphabet} a}}%
  \eng{Returns the word whose standard permutation is \Mpar{p} and
    whose evaluation (as an integer vector) is \Mpar{e}.}
\end{MMethodDetails}

\MethodSection{Shuffle product of words}

\begin{MMethodDetails}{shuffle}
  \infoEng{shuffle product of two words}
  \call{\Mtype{word} w1, \Mtype{word} w2}%
  \eng{Returns the list of the words in the shuffle product of
    \Mpar{w1} and \Mpar{w2}.}
\end{MMethodDetails}

\begin{MMethodDetails}{shuffle::generator}
  \infoEng{generator for the shuffle product of two words}
  \call{\Mtype{word} w1, \Mtype{word} w2}%
  \eng{Returns a generator for the words in the shuffle product of
    \Mpar{w1} and \Mpar{w2}.}
\end{MMethodDetails}

\begin{MMethodDetails}{shuffleAugmented}
  \infoEng{augmented shuffle product of two words}
  \call{\Mtype{word} w1, \Mtype{word} w2}%
  \eng{Returns the list of the words in the augmented shuffle product
    of \Mpar{w1} and \Mpar{w2}.}
\end{MMethodDetails}

\MethodSection{Comparison of words}

\begin{MMethodDetails}{lexLess}[ImplState=beta,TestState=beta,DocState=beta]
  \infoEng{strict lexicographic comparison of words}
  \call{\Mtype{word} w1, \Mtype{word} w2}%
  \eng{Returns TRUE if \Mpar{w1} is strictly smaller than \Mpar{w1} w.r.t. the
    lexicographic order.}%
  \eng{All the comparison functions currently require that the letters
    in \Mpar{w1} and \Mpar{w1} should be comparable with \Mex{<}. The
    degree comparison functions further require that the letters can
    be added with \Mex{+}, and the result compared with \Mex{<}.
    Finally, to compare lists of different size, we use consistently
    the convention that a non existent letter is strictly smaller than
    an existent letter.}
\end{MMethodDetails}

\begin{MMethodDetails}{degLexLess}[ImplState=beta,TestState=beta,DocState=beta]
  \infoEng{strict degree lexicographic comparison of words}
  \call{\Mtype{word} w1, \Mtype{word} w2}%
  \eng{Returns TRUE if \Mpar{w1} is strictly smaller than \Mpar{w1} w.r.t. the
    degree lexicographic order.}
  \eng{See \Mup{combinat::words::lexLess} for the constraints on the letters.}
\end{MMethodDetails}

\begin{MMethodDetails}{invLexLess}[ImplState=beta,TestState=alpha,DocState=beta]
  \infoEng{strict inverse lexicographic comparison of words}
  \call{\Mtype{word} w1, \Mtype{word} w2}%
  \eng{Returns TRUE if \Mpar{w1} is strictly smaller than \Mpar{w1}
    w.r.t. the inverse lexicographic order.}
  \eng{See \Mup{combinat::words::lexLess} for the constraints on the letters.}
\end{MMethodDetails}

\begin{MMethodDetails}{degInvLexLess}[ImplState=beta,TestState=beta,DocState=beta]
  \infoEng{strict degree inverse lexicographic comparison of words}
  \call{\Mtype{word} w1, \Mtype{word} w2}%
  \eng{Returns TRUE if \Mpar{w1} is strictly smaller than \Mpar{w1} w.r.t. the
    degree inverse lexicographic order.}
  \eng{Currently, the letters in \Mpar{w1} and \Mpar{w1} should be
    comparable with \Mex{<}, and addable by \Mex{+}.}
\end{MMethodDetails}

\begin{MMethodDetails}{revLexLess}[ImplState=beta,TestState=alpha,DocState=beta]
  \infoEng{strict reverse lexicographic comparison of words}
  \call{\Mtype{word} w1, \Mtype{word} w2}%
  \eng{Returns TRUE if \Mpar{w1} is strictly smaller than \Mpar{w1}
    w.r.t. the reverse lexicographic order.}
  \eng{See \Mup{combinat::words::lexLess} for the constraints on the letters.}
\end{MMethodDetails}

\begin{MMethodDetails}{degRevLexLess}[ImplState=beta,TestState=alpha,DocState=beta]
  \infoEng{strict degree reverse lexicographic comparison of words}
  \call{\Mtype{word} w1, \Mtype{word} w2}%
  \eng{Returns TRUE if \Mpar{w1} is strictly smaller than \Mpar{w1} w.r.t. the
    degree reverse lexicographic order.}
  \eng{See \Mup{combinat::words::lexLess} for the constraints on the letters.}
\end{MMethodDetails}

\MethodSection{Miscellaneous}

\begin{MMethodDetails}{fromStandard}[ImplState=stable,TestState=stable,DocState=alpha]
\end{MMethodDetails}

\begin{MMethodDetails}{swap}[DocState=beta]
  \infoEng{swap two consecutive letters in a word}
  \call{\Mtype{word} w, \Mtype{integer} i}%
  \eng{Swap the entries at positions \Mpar{i} and \Mpar{i+1} in the word \Mpar{w}}
\end{MMethodDetails}

\begin{MMethodDetails}{swapIncrease}[DocState=beta]
  \infoEng{swap two consecutive letters in a word}
  \call{\Mtype{word} w, \Mtype{integer} i}%
  \eng{Swap the entries at positions \Mpar{i} and \Mpar{i+1} in the
    word \Mpar{w} if \Mex{w[i]>w[i+1]}.}
  \eng{This method is likely to be renamed.}
\end{MMethodDetails}

\begin{MMethodDetails}{swapDecrease}[DocState=beta]
  \infoEng{swap two consecutive letters in a word}
  \call{\Mtype{word} w, \Mtype{integer} i}%
  \eng{Swap the entries at positions \Mpar{i} and \Mpar{i+1} in the
    word \Mpar{w} if \Mex{w[i]<w[i+1]}.}
  \eng{This method is likely to be renamed.}
\end{MMethodDetails}

\begin{MMethodDetails}{hammingDistance}[DocState=beta]
  \infoEng{Hamming distance between two words}
  \call{\Mtype{word} w1, \Mtype{word} w2}%
  \eng{Returns the Hamming distance between the words \Mex{w1} and
    \Mex{w2}. This is the number of positions where the two words
    differ. If one word is longer than the other, then its extra
    letters are considered as different from the missing ones of the
    other.}
\end{MMethodDetails}

\begin{MMethodDetails}{fromStandard}[ImplState=stable,TestState=stable,DocState=alpha]
\end{MMethodDetails}

\begin{MExample}{word-basic}
  \eng{There are $8$ words of length $3$ on the alphabet
    \Mex{\{a,b\}}:}
  \begin{Mexin}
combinat::words::count([a,b],3)
  \end{Mexin}
  \begin{Mexout}
                               8
  \end{Mexout}
  \eng{Here is the list:}
  \begin{Mexin}
combinat::words::list([a,b],3)
  \end{Mexin}
  \begin{Mexout}
[[a, a, a], [a, a, b], [a, b, a], [a, b, b], [b, a, a],

   [b, a, b], [b, b, a], [b, b, b]]
  \end{Mexout}
  \eng{For the alphabet of \Mex{[1,2]}, it is shorter to write:}
  \begin{Mexin}
combinat::words::count(2,3);
combinat::words::list(2,3);
  \end{Mexin}
  \begin{Mexout}
                               8

[[1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 2, 2], [2, 1, 1],

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

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

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

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

                           [1, 1, 1]

[1, 1, 2], [1, 2, 1], [1, 2, 2], [2, 1, 1], [2, 1, 2],

   [2, 2, 1], [2, 2, 2], FAIL
  \end{Mexout}

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

                            [1, 2]

                            [2, 1]

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


\begin{MExample}{words-order}
  \eng{Most operations on words, such as standardization, depends on
    an alphabet ordering. You can get the ordering function associated
    with an alphabet with \Mex{combinat::words::alphabetToOrder}:}
  \begin{Mexin}
isSmaller := combinat::words::alphabetToOrder([c,b,a,d]):
isSmaller(a,b), bool(isSmaller(a,b));
isSmaller(a,d), bool(isSmaller(a,d));
  \end{Mexin}
  \begin{Mexout}
                         3 < 2, FALSE

                          3 < 4, TRUE
  \end{Mexout}
  \eng{Note that \Mex{isSmaller} does not return a boolean value but
    rather an expression whose evaluation is boolean.}

  \eng{If the alphabet is given by means of a set, an unspecified fixed
  order is chosen:}
  \begin{Mvin}{test=false}
isSmaller := combinat::words::alphabetToOrder({c,b,a,d}):
isSmaller(a,b), bool(isSmaller(a,b));
isSmaller(a,d), bool(isSmaller(a,d));
  \end{Mvin}
  \begin{Mvout}{test=false}
                          2 < 3, TRUE

                         2 < 1, FALSE
  \end{Mvout}
\end{MExample}

\begin{MExample}{standardization}
  \eng{You can compute the standard permutation of a word:}
  \begin{Mexin}
combinat::words::standard([1,2,3,2,2,1,2,1])
  \end{Mexin}
  \begin{Mexout}
                   [1, 4, 8, 5, 6, 2, 7, 3]
  \end{Mexout}
  \eng{The standard permutation of a word and the word itself have by
    definition the same inversions (see
    \Mup{combinat::permutations::inversions}):}
  \begin{Mexin}
combinat::permutations::inversions([1,2,3,2,2,1,2,1]);
combinat::permutations::inversions(
   combinat::words::standard([1,2,3,2,2,1,2,1]));
  \end{Mexin}
  \begin{Mexout}
[{2, 6}, {2, 8}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {3, 8},

   {4, 6}, {4, 8}, {5, 6}, {5, 8}, {7, 8}]

[{2, 6}, {2, 8}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {3, 8},

   {4, 6}, {4, 8}, {5, 6}, {5, 8}, {7, 8}]
  \end{Mexout}
  \eng{If your word is on an alphabet which cannot be ordered with
    \Mup{<}, you have to specify the order:}
  \begin{Mexin}
combinat::words::standard([a,b,a,c,b,c,a]);
  \end{Mexin}
  \begin{Mexout}
Error: Can't evaluate to boolean [_less];
during evaluation of 'combinat::words::standard'
  \end{Mexout}
  \eng{You can do that by specifying explicitly the alphabet:}
  \begin{Mexin}
combinat::words::standard([a,b,a,c,b,c,a],[a,b,c,d]);
  \end{Mexin}
  \begin{Mexout}
                     [1, 4, 2, 6, 5, 7, 3]
  \end{Mexout}
  \eng{Another way is to provide an ordering function:}
  \begin{Mexin}
isSmaller := (x,y) -> (expr2text(x) < expr2text(y)):
combinat::words::standard([a,b,a,c,b,c,a],isSmaller);
  \end{Mexin}
  \begin{Mexout}
                     [1, 4, 2, 6, 5, 7, 3]
  \end{Mexout}
\end{MExample}  

\begin{MExample}{shuffle}
  \eng{You can compute the shuffle product of two words:}
  \begin{Mexin}
combinat::words::shuffle([1,2,3],[a,b]);
  \end{Mexin}
  \begin{Mexout}
[[1, 2, 3, a, b], [1, 2, a, 3, b], [1, 2, a, b, 3],

   [1, a, 2, 3, b], [1, a, 2, b, 3], [1, a, b, 2, 3],

   [a, 1, 2, 3, b], [a, 1, 2, b, 3], [a, 1, b, 2, 3],

   [a, b, 1, 2, 3]]
  \end{Mexout}
  You can also obtain them through a generator:
  \begin{Mexin}
g:=combinat::words::shuffle::generator([1,2,3],[a,b]):
g(); g();
g() $ i=1..9;
  \end{Mexin} %$
  \begin{Mexout}
                        [1, 2, 3, a, b]

                        [1, 2, a, 3, b]

[1, 2, a, b, 3], [1, a, 2, 3, b], [1, a, 2, b, 3],

   [1, a, b, 2, 3], [a, 1, 2, 3, b], [a, 1, 2, b, 3],

   [a, 1, b, 2, 3], [a, b, 1, 2, 3], FAIL
  \end{Mexout}

  Finally, here is the list of the words in the augmented shuffle
  product of \Mex{[1,2]} and \Mex{[a,b]}:
    \begin{Mexin}
combinat::words::shuffleAugmented([1, 2], [a, b])
  \end{Mexin}
  \begin{Mexout}
[[a, b, 1, 2], [a, 1, b, 2], [1, a, b, 2], [a + 1, b, 2],

   [a, b + 1, 2], [a, 1, 2, b], [1, a, 2, b], [a + 1, 2, b],

   [1, 2, a, b], [1, a + 2, b], [a, 1, b + 2], [1, a, b + 2],

   [a + 1, b + 2]]
  \end{Mexout}

\end{MExample}

\MSuperDomain{Dom::BaseDomain}

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


\end{Mhelppage}

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