% $Id: PermutationGroup.tex,v 1.1.1.4 2004/10/04 17:25:13 nthiery Exp $
\begin{Mhelppage}{PermutationGroup}{S.~Wehmeier}
%  [ImplState=stable,TestState=stable,DocState=stable]
\Mproofread{kg}{18.5.00}{siehe todo}

\begin{MInfo}
\eng{permutation group}
\de{}
\end{MInfo}

\begin{todo}
- Detail z. Domain fehlen
- Anmerkungen zur Ueberladung fehlen
- Auflistung der Methoden nicht vollstaendig
- s. diverse handschriftliche Anmerkungen f. d. Autor (kg)
\end{todo}

\begin{MIntro}
\eng{\Mthis\Mex{(n, generators\Mopt{, options})}
  creates a domain for the group of permutations of $\{1,\ldots,n\}$
  generated by \Mpar{generators}.}
\end{MIntro}

\begin{MDomConst}
  \MCall{n}
\end{MDomConst}

\begin{MParameters}
 \param{n}
\eng{positive integer}
\de{positive ganze Zahl}
 \param{generators}
\eng{list of permutations of $\{1,\ldots,n\}$}
\end{MParameters}

\begin{MDetails}
  \eng{A permutation of $n$ elements is a bijective mapping of the set
    $\{1,\ldots,n\}$ onto itself.}
  \de{}
\end{MDetails}

\begin{MIntro}
\eng{The domain element \Mthis\Mex{(n)(l)} represents the bijective
mapping of the first $n$ positive integers that maps the integer $i$
to \Mex{l[i]}, for $1 \leq i \leq n$.}
\de{}
\end{MIntro}

\begin{MDomElConst}
\MCall[\Mthis(n)]{l}
\end{MDomElConst}

\begin{MParameters}
\param{l}
\eng{list or array consisting of the first $n$ integers in some order.}
\de{}
\end{MParameters}

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

\MRelatedDomains{Dom::DihedralGroup,Dom::SymmetricGroup,combinat::permutations}

%\begin{MDetails}
%\eng{}
%\de{}
%\end{MDetails}

\begin{MDomEntries}
\MDomEntry{one}
\eng{the identical mapping of the set $\{ 1, \ldots , n \} $ to itself.}
\de{}
\end{MDomEntries}


\MMathMethods

\begin{MMethodDetails}{_mult}
  \infoEng{product of permutations}
    \infoDe{}  
\call{\Mseq{\Mtype{dom} a1}}
\eng{The product \Mex{a1*a2*\ldots{}*ak} of permutations is defined to
    be the mapping that assigns, to every integer \Mex{i} between $1$
    and $n$, the integer \Mex{a1(a2(\ldots ak(i)
    \ldots))}.}
\de{}
\eng{This method overloads the function \Mup{_mult}.}
\end{MMethodDetails}

\begin{MMethodDetails}{_invert}
\infoEng{inverse of a permutation}
\infoDe{}

\call{\Mtype{dom} a}
\eng{ This method computes a permutation \Mex{b} such that \Mex{a*b}
is the identity mapping.}
\de{}
\eng{This method overloads the function \Mup{_invert}.}
\end{MMethodDetails}

\begin{MMethodDetails}{func_call}
\infoEng{function value of a permutation at a point}
\infoDe{}

\call{\Mtype{dom} a, \Mtype{integer} i}
\eng{This method overloads the round brackets \Mex{(\ldots)}, i.e. it
may be called in the form \Mex{a(i)}.}
\eng{It computes the function value
of \Mex{a} at \Mex{i}, i.e., the integer that \Mex{i} is mapped to by
the permutation \Mex{a}; \Mex{i} must be an integer between $1$ and 
$n$.} 
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{cycles}
\infoEng{cycle representation of a permutation}
\infoDe{}
\call{\Mtype{dom} a}
\eng{ This method computes a cycle representation of \Mex{a}. A cycle
representation is a list \Mex{[orbit1, \ldots , orbitk]}; each of the
orbits is a list of integers of the form \Mex{[i, a(i), a(a(i)),
\ldots ]} with just as many elements such that \Mex{i} does not occur
in it
for a second time; and each integer between $1$ and $n$ appears in
exactly one of the orbits.}
\de{}
\end{MMethodDetails}


\begin{MMethodDetails}{order}
\infoEng{order of a permutation}
\infoDe{}
\call{\Mtype{dom} a}
\eng{The order of \Mex{a} is defined to be the least positive integer
\Mex{k} for which $a^k$ is the identity.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{inversions}
\infoEng{number of inversions}
\infoDe{}
\call{\Mtype{dom} a}
\eng{This method computes the number of all pairs $i,j$ of integers
for which $i<j$ but $a(i) > a(j)$.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{sign}
\infoEng{sign of a permutation}
\infoDe{}
\call{\Mtype{dom} a}
\eng{This method returns the sign of the permutation \Mex{a}. The sign
of a permutation is defined to be $1$ if its number of inversions is
even, and $-1$ otherwise.} 
\de{} 
\end{MMethodDetails}


% fehlt noch: descent, descentPoly, allElements

 \begin{MMethodDetails}{random}
    \infoEng{random permutation}
    \infoDe{}

\call{}
\eng{This method returns a random element of the permutation group.}
\de{}
 \end{MMethodDetails}



\MAccessMethods

\begin{MMethodDetails}{allElements}
\infoEng{elements of the group}
\infoDe{}
\call{}
\eng{This method returns the list of the elements of the group.}
\de{} 
\end{MMethodDetails}

\begin{MMethodDetails}{size}
\infoEng{size of the group}
\infoDe{}
\call{}
\eng{This method returns the size of the group.}
\de{} 
\end{MMethodDetails}

\MConvMethods

\begin{MMethodDetails}{convert}  
  \infoEng{conversion of an object into a permutation}
  \infoDe{}

\call{\Mtype{any} x}
\eng{This method tries to convert \Mex{x} into a permutation. This is
only possible if \Mex{x} is a list or an array in which each of the
integers $1$ through $n$ occurs exactly once.}
\de{}
  \end{MMethodDetails}

\begin{MMethodDetails}{convert_to}
    \infoEng{conversion of a permutation into another type}
    \infoDe{}
\call{\Mtype{dom} a, \Mtype{any} T}
\eng{ Tries to convert \Mex{a} into type \Mex{T}. Currently, only a
    conversion into a list of type \Mup{DOM_LIST} is possible.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{expr}
\infoEng{convert a permutation into a list}
\infoDe{}
\call{\Mtype{dom} a}
\eng{ This method returns a list such that generating a permutation
from that 
list would result in \Mex{a}.}
\de{}
\end{MMethodDetails}


\begin{MExample}{ex1}
\eng{We construct the cyclic group of order $4$, generated by the
  cycle $(1,2,3,4)$.:}
\de{}
  \begin{Mexin}
G := Dom::PermutationGroup(4, [[[1,2,3,4]]])
  \end{Mexin}
  \begin{Mexout}
          Dom::PermutationGroup(4, [[[1, 2, 3, 4]]])
  \end{Mexout}
  \eng{It has $4$ elements:}
  % The order of the elements in the output depends on whether we
  % are using GLIP or not; not tested anymore.
  \begin{Mvin}{test=false}
G::size;
G::allElements();
  \end{Mvin}
  \begin{Mvout}{test=false}
                               4

   [[2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3], [1, 2, 3, 4]]
  \end{Mvout}
  
  \eng{We construct a permutation of \Mex{G} by providing the images
    of $1$, $2$, etc.:}
  \begin{Mexin}
p := G([3,4,1,2]);
p(1), p(2), p(3), p(4);
  \end{Mexin}
  \begin{Mexout}
                         [3, 4, 1, 2]

                          3, 4, 1, 2
  \end{Mexout}

  \eng{We construct a permutation from its cycle notation:}
  \begin{Mexin}
G([[1,2],[3,4]])
  \end{Mexin}
  \begin{Mexout}
                         [2, 1, 4, 3]
  \end{Mexout}
\end{MExample}

\MSuperDomain{Dom::BaseDomain}

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

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

\begin{MChanges}
  \version{2.0}
  \none
  \version{2.5}%
  \eng[NewFunctionality]{This domain now covers all permutation groups,
    and not only the symmetric groups. Creating a symmetric group with
    \Mupc{Dom::PermutationGroup}{n} is temporarily retained for
    backward compatibility; however, this usage is strongly deprecated
    in favor of \Mupc{Dom::SymmetricGroup}{n}. The emission of a
    warning can be controlled with
    \Mupc{combinat::warnDeprecated}{FALSE} or
    \Mupc{combinat::warnDeprecated}{TRUE}.}
\end{MChanges}

\end{Mhelppage}
