%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% $Id $
% File:		lib/COMBINAT/DOC/necklaces.tex
% Authors:	Nicolas M. Thiéry <nthiery@users.sourceforge.net>
% Purpose:	Documentation for the domain combinat::necklaces
% Created:	Wed Jan 28 23:42:48 2004
% License:	LGPL
% Project:	MuPAD-Combinat, http://mupad-combinat.sf.net
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{Mhelppage}{necklaces}{N.~Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
%\Mproofread{...}{...}{...}

\begin{MInfo}
  \eng{necklaces}
  \de{}
\end{MInfo}

\begin{MIntro}
  \eng{\Mthis{} provides functions for counting, generating, and
    manipulating necklaces.}
  \de{}
  \eng{Further functions are documented theme by theme in separate help
    pages:
    \begin{itemize}
    \item necklaces with prescribed evaluation:
      \Mup{combinat::necklaces::fromEvaluation}.
    \item necklaces with prescribed content:
      \Mup{combinat::necklaces::fromContent}.
    \end{itemize}}
\end{MIntro}

\MKeywords{combinatorics, necklaces}

\begin{MDetails}
  \eng{A \emph{necklace} is a word, considered up to a cyclic
    rotation. For example, \Mex{[2,1,3,1]}, \Mex{[1,3,1,2]},
    \Mex{[3,1,2,1]}, and \Mex{[1,2,1,3]} all represent the same
    necklace.}
  \eng{If the letters (or \emph{beads}) of a necklace can be ordered
    then, by convention, its canonical representative is the
    lexicographically smallest element in its equivalence class. In
    the example above, that would be \Mex{[1,2,1,3]}.}
  \eng{A necklace may be periodic, like \Mex{[1,2,1,2,1,2]}. See
    \Mup{combinat::lyndonWords} for manipulating aperiodic necklaces.}
\end{MDetails}

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

\MRelatedDomains{combinat::lyndonWords}

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

\MSuperDomain{Dom::BaseDomain}

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


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

\end{Mhelppage}


\begin{Mhelppage}{necklaces::fromEvaluation}{X.~Molinero and N~.Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
%\Mproofread{...}{...}{...}

\begin{MInfo}
  \eng{necklaces with prescribed evaluation}
\end{MInfo}

\begin{MIntro}
  \eng{The combinatorial class of integral necklaces with
    prescribed evaluation}
\end{MIntro}

\begin{MDetails}
  \eng{An \emph{integer necklace} is a necklace whose operands
    are positive integers.} %
  
  \eng{The \emph{evaluation} of a necklace \Mex{w} is a list \Mex{c}
    such that \Mex{c[i]} is the number of occurrences of the letter
    \Mex{i} in \Mex{w}. For example, the evaluation of
    \Mex{[1,1,1,2,1,3,3]} is \Mex{[4,1,2]}. See
    \Mup{combinat::words::evaluation} for details.} %
  
  \eng{Some functions here only deal with evaluations that are
    compositions. In other words the corresponding Lyndon words should
    contain all the integers in a range \Mex{1..k} (counter examples:
    \Mex{[2,2,3]} or \Mex{[1,4,3,3]}).}
\end{MDetails}

\begin{MMethodDetails}{isA}
  \infoEng{test if an object is a necklace}
  \call{\Mtype{any type} object, \Mopt{\Mtype{composition} evaluation}}
  \eng{Returns whether \Mpar{object} is a necklace.}
  \eng{If the optional argument is present, returns whether
    \Mpar{object} is a necklace with evaluation \Mpar{evaluation}.}
\end{MMethodDetails}

\begin{MMethodDetails}{count}
  \infoEng{number of integer necklaces with prescribed evaluation}
  \call{\Mtype{integer list} evaluation}
  \eng{Returns the number of integer necklaces with evaluation
    \Mex{evaluation}.}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of the integer necklaces with prescribed evaluation}
  \call{\Mtype{composition} evaluation}
  \eng{Returns the list of the integer necklaces with evaluation
    \Mex{evaluation}.}
\end{MMethodDetails}

\begin{MMethodDetails}{generator}
  \infoEng{generator for the integer necklaces with prescribed evaluation}
  \call{\Mtype{composition} evaluation}
  \eng{Returns a generator for the integer necklaces with evaluation
    \Mex{evaluation}.}
\end{MMethodDetails}

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

\begin{MExample}{ex-basic}
  \eng{There are $3$ necklaces with three 1's and three 2's:}
  \begin{Mexin}
combinat::necklaces::fromEvaluation::list([3, 3])
  \end{Mexin}
  \begin{Mexout}
[[1, 2, 1, 2, 1, 2], [1, 1, 2, 2, 1, 2], [1, 1, 2, 1, 2, 2],

   [1, 1, 1, 2, 2, 2]]
  \end{Mexout}
  \eng{On the other hand, \Mex{[1,1,1]} is periodic, so there are no
    necklace with three 1's:}
  \begin{Mexin}
combinat::necklaces::fromEvaluation::list([3])
  \end{Mexin}
  \begin{Mexout}
                          [[1, 1, 1]]
  \end{Mexout}
\end{MExample}

\MSuperDomain{Dom::BaseDomain}

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

\begin{MBackground}
  \eng{The generation algorithm for necklaces with prescribed
    evaluation is guaranteed to be constant time amortized for each
    necklace generated if the last entry of the evaluation is the
    largest one. As a consequence, to generate all the necklaces with
    letters \Mex{[2,2,2,1,1]}, it is more efficient to generate the
    necklaces with letters \Mex{[1,1,2,2,2]}, and to relabel them
    accordingly afterward. Of course, the downside is that the
    resulting necklaces are not in canonical form.}
  
  \eng{Reference: Joe Sawada, A fast algorithm to generate necklaces
    with fixed content, Theoretical Computer Science, 2003, 301, pp.\ 
    477-489.}
  
  \eng{As far as we can tell, there is no known good algorithm for
    unranking necklaces and Lyndon words with prescribed evaluation.}
\end{MBackground}

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

\end{Mhelppage}

\begin{Mhelppage}{necklaces::fromContent}{X.~Molinero and N~.Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
%\Mproofread{...}{...}{...}

\begin{MInfo}
  \eng{necklaces with prescribed content}
\end{MInfo}

\begin{MIntro}
  \eng{The combinatorial class of integral necklaces with
    prescribed content}
\end{MIntro}

\begin{MDetails}
  \eng{This domain is a wrapper around
    \Mup{combinat::necklaces::fromEvaluation} to make it easy to
    generate necklaces by content; the available methods are the same,
    but take contents instead of evaluations as arguments.} %
  
  \eng{To decide on the canonical representative of a necklace, the
    letters appearing in the content are ordered as in \Mex{sort}.}
\end{MDetails}

\begin{MExample}{ex-fromContent}
  Here are all the necklaces containing three \Mex{a}'s, one \Mex{b},
  and two \Mex{d}'s:
  \begin{Mexin}
combinat::necklaces::fromContent([a, a, a, b, d, d])
  \end{Mexin}
  \begin{Mexout}
[[a, b, a, d, a, d], [a, a, d, d, a, b], [a, a, d, b, a, d],

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

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

   [a, a, a, b, d, d]]
  \end{Mexout}
\end{MExample}


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

\end{Mhelppage}
