path: root/macros/latex/contrib/permute/permute.dtx

% \iffalse
%
%   permute.dtx and permute.ins and all files generated from these files are
%   referred to as `the permute package'. It is distributed under the terms
%   of the \LaTeX\ Project Public License from CTAN archives in directory
%   macros/latex/base/lppl.txt. Either version 1.0 or, at your option, any
%   later version. The use of the package is completely free.
%
%   Permission is granted to modify the permute package. You are not allowed to
%   distribute any changed version of the package, neither under the same name
%   nor under a different one.
%
%   Send comments, ideas and bug reports via electronic mail to
%
%       cheinz@gmx.de
%
%   (w)(c) 1997--1999 by Carsten Heinz
%
%<*driver>
\documentclass{ltxdoc}

\usepackage{permute}[1999/11/10]

\EnableCrossrefs
\CodelineIndex
\OnlyDescription

\begin{document}
    \DocInput{permute.dtx}
\end{document}
%</driver>
% \fi
%
% \newbox\abstractbox
% \setbox\abstractbox=\vbox{
% \begin{abstract}
%   The \textsf{permute} package inputs, outputs and composes permutations.
%   For example, |$\pmt{(123)}\circ\pmt{(321)} = \pmt{(123)(321)}$| produces
%   $\pmt{(123)}\circ\pmt{(321)}=\pmt{(123)(321)}$. A misleading example is
%   $(a\ldots z)\circ(z\ldots a)=\pmt{(a\ldots z)(z\ldots a)}$ printed via
%   |$(a\ldots z)\circ(z\ldots a)=\pmt{(a\ldots z)(z\ldots a)}$|
%   --- misleading since the package doesn't care about the human
%   interpretation of ``\ldots''.
% \end{abstract}}
%
% \title{The \textsf{Permute} Package}
% \author{Copyright 1997--1999 by Carsten Heinz}
% \date{Version 0.12\\ \box\abstractbox}
% \maketitle
%
%^^A
%^^A private adjustments
%^^A
% \makeatletter
% \renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}^^A
%                                       {1.25ex \@plus1ex \@minus.2ex}^^A
%                                       {-1em}^^A
%                                       {\normalfont\normalsize\bfseries}}
% \makeatother
% \newenvironment{syntax}{\list{}{\itemindent-\leftmargin}}{\endlist}
%
%
% \section{User's guide}
%
%
% \subsection{Software license}
%
% \texttt{permute.dtx} and \texttt{permute.ins} and all files generated from
% these files are referred to as `the \textsf{permute} package'.
% It is distributed under the terms of the \LaTeX\ Project Public License
% from CTAN archives in directory \texttt{macros/latex/base/lppl.txt}.
% Either version 1.0 or, at your option, any later version.
% The use of the package is completely free.
%
% Permission is granted to modify the \textsf{permute} package.
% You are not allowed to distribute any changed version of the package,
% neither under the same name nor under a different one.
%
% Send comments, ideas and bug reports via electronic mail to
% \texttt{cheinz@gmx.de}.
%
%
% \subsection{Installation}
%
% \begin{enumerate}
% \item Following the \TeX\ directory structure (TDS) you should put the files
%       of the package into directories as follows:
%       \begin{center}
%       \begin{tabular}{l@{\quad$\to$\quad}l}
%       \texttt{permute.dvi}
%           & \texttt{texmf/doc/latex/permute}\\
%       \texttt{permute.dtx}, \texttt{permute.ins}
%           & \texttt{texmf/source/latex/permute}\\
%       \end{tabular}
%       \end{center}
%       Of course, you need not to use the TDS.
%       Simply adjust the directories below.
% \item	Create the directory \texttt{texmf/tex/latex/permute}.
% \item	Change the working directory to \texttt{texmf/source/latex/permute}
%       and run \texttt{permute.ins} through \TeX.
% \item Move the generated file to \texttt{texmf/tex/latex/permute} if this
%       is not already done.
% \item If your \TeX\ implementation uses a filename database, update it.
% \end{enumerate}
%
%
% \subsection{Input and output formats}
%
% \paragraph{General notation.}
% First we restrict ourselves to $S_1,\ldots,S_9$:
%    $$S_n:=\{f:\{1,\ldots,n\}\to\{1,\ldots,n\}\,\vert\,
%             f\textrm{ is one-to-one and onto}\}.$$
% A permutation $f\in S_n$ can be written \textbf{verbose} as an explicit
% sequence of pre-image/image pairs like this:
%    $$f=\pmtv[12\ldots n]{1{f(1)} 2{f(2)} \ldots\ldots n{f(n)}}.$$
% A permutation $\sigma$ is a \textbf{cycle} and written
%    $\sigma=(x_1x_2\ldots x_k)$
% if and only if there are distinct numbers
%   $x_1,x_2,\ldots,x_k\in\{1,\ldots,n\}$
% satisfying
%   \begin{eqnarray*}
%   \sigma(x_i)&=&x_{i+1}\qquad\textrm{ for all }1\leq i<k\\
%   \sigma(x_k)&=&x_1\\
%   \sigma(x)&=&x\hphantom{\mbox{$_{i+1}$}}\qquad%
%       \textrm{ for all }x\in\{1,\ldots,n\}\setminus\{x_1,\ldots,x_k\}.
%   \end{eqnarray*}
% This means that a cycle $(x_1x_2\ldots x_k)$ maps
%   $x_1$ to $x_2$, $x_2$ to $x_3$, \ldots, $x_k$ back to $x_1$,
% and fixes all other elements.
% Each permutation in $S_n$ can be written as a composition of cycles, for
% example $\pmtv[12345]{12 21 35 43 54}=(12)\circ(354)=(12)(354)$---we leave
% out the ``$\circ$''.
% Note that $S_n$ is not commutative in general and that we compose from the
% right to the left.
% In the example 3 is mapped to 5 and then 5 stays 5 since unchanged by (12).
%
% \paragraph{Input formats.}
% If you want to enter a permutation cycle based, just write the cycles after
% each other.
% |(12)(354)| would be legal; there must not be a |\circ| in between.
% The verbose input format lists all pre-image/image pairs without any
% separators, but a space is allowed in between.
% The permutation above could also be entered as |12 21 35 43 54|.
% The package distinguishes the two formats by looking at the first token:
% If and only if it's a left parenthesis, the package accepts cycles.
%
% Now we drop the restriction $n\leq 9$ and the limitation of permuting
% numbers; we can do it with nearly arbitrary (token) strings.
% To enter a string as pre-image, image or inside a cycle, enclose
% the string in braces. That's all!
% For example, I typed
% \begin{verbatim}
%    1{f(1)} 2{f(2)} \ldots\ldots n{f(n)}\end{verbatim}
% for $\pmtv[12\ldots n]{1{f(1)} 2{f(2)}\ldots\ldots n{f(n)}}$, which actually
% isn't a permutation at all.
%
% In the sequel \meta{pmt} means either a verbose sequence or a sequence of
% cycles.
% \emph{Do not use} |\empty| \emph{or} |\relax| \emph{or equivalent
% definitions inside} \meta{pmt}.
%
% \paragraph{Output formats.}
% The package provides a cycle based and two verbose output formats.
% Some of the commands described below have an optional \meta{print order}
% argument.
% Now let \meta{print order} equal $n_1n_2\ldots n_k$ where each $n_i$ is a
% single token or a braced string.
% If $n_i$ and $n_{i+1}$ both appear in a permutation and appear in different
% cycles, then the cycle containing $n_i$ is printed first.
% Moreover the cycle starts with the element $n_i$.
% Cycles not covered by \meta{print order} are printed as they appear in the
% internal data format.
% Some examples on printing (12)(34)(56):
% \begin{center}
% \begin{tabular}{ll@{\qquad\qquad}ll}
% \meta{print order}  & results in & \meta{print order} & results in\\
% no order & \pmt{(12)(34)(56)}    & empty & \pmt[]{(12)(34)(56)}\\
%      |2| & \pmt[2]{(12)(34)(56)} & |23|  & \pmt[23]{(12)(34)(56)}\\
%      |6| & \pmt[6]{(12)(34)(56)}\\
% \end{tabular}
% \end{center}
% All results represent the same permutation.
% Note the difference between `no order' and `empty':
% The package uses a standard order if you don't request a special one.
%
% There is some danger if you want to use a \emph{single token string} as
% \meta{print order}. In this case you must enclose the string in
% \emph{two level} of braces. Use \meta{print order}$=$|{{one}}| to control
% |({one}{two})({two}{three})({three}{four})|, for example. Since \TeX\ 
% discards one group level, |{one}| would lead to the order |o|, |n|, |e|.
% However, \meta{print order}$=$|{one}{two}| needs no extra braces.
%
% \medbreak
% For the verbose output formats, \meta{print order} plays the role of domain.
% The package uses exactly the elements and order, i.e.\ all pre-images not
% appearing in \meta{print order} are not printed, and we assume image=pre-image
% if pre-image appears in \meta{print order} but not in the permutation.
% Some examples on printing |1{f(1)} 2{f(2)} \ldots\ldots n{f(n)}|:
% \begin{center}
% \begin{tabular}{ll}
% \meta{print order}&results in\\
% no order        & \pmtv{1{f(1)} 2{f(2)} \ldots\ldots n{f(n)}}\\ \noalign{\smallskip}
% |n\ldots 21|    & \pmtv[n\ldots21]{1{f(1)} 2{f(2)} \ldots\ldots n{f(n)}}\\ \noalign{\smallskip}
% |2\ldots n{n+1}|& \pmtv[2\ldots n{n+1}]{1{f(1)} 2{f(2)} \ldots\ldots n{f(n)}}\\ \noalign{\smallskip}
% empty           & \pmtv[]{1{f(1)} 2{f(2)} \ldots\ldots n{f(n)}}
% \end{tabular}
% \end{center}
% The first example doesn't print `$\ldots$' and `$f(n)$' since the pre-images
% `$\ldots$' and `$n$' don't appear in the standard printing order (which is
% the domain here).
% But it shows image=pre-image pairs not in the permutation since the standard
% domain defines the elements as pre-images.
%
% Note:
% (a) The (full) verbose format uses math mode and the \TeX-primitive |\atop|.
% The latter causes a warning if used together with \texttt{amsmath.sty}.
% (b) The package defines a short verbose output format, too.
% It prints the row of images only.
% Don't take it for the cycle based format!
%
% \medbreak
% Finally, some commands also have a star-form which separate the output like
% this: \pmt*{(12)(23)(34)}.
% It is useful if you use strings instead of numbers, for example the
% permutation \pmt*[{{one}}]{({one}{two})({two}{three})({three}{four})} is
% printed with a |*|-command.
%
%
% \subsection{User commands}
%
% \begin{syntax}
% \item |\pmt|[|*|][\oarg{print order}]\marg{pmt}
%
%       calculates the composition of the cycles (if any) and prints the
%       permutation:
%           |\pmt{(12)(23)(34)}| prints \pmt{(12)(23)(34)} and
%           |\pmt{12 23 34 41}| gives \pmt{12 23 34 41}.
%       Note that this command outputs cycles only.
%       Some examples:
% \begin{center}
% \begin{tabular}{l@{\ prints\ }p{0.4\linewidth}}
% |\pmt{(12)(34)(56)}|&\pmt{(12)(34)(56)}\\
% |\pmt*[2]{(12)(34)(56)}|&\pmt*[2]{(12)(34)(56)}\\
% |\pmt[23]{(12)(34)(56)}|&\pmt[23]{(12)(34)(56)}\\
% |\pmt*[6]{(12)(34)(56)}|&\pmt*[6]{(12)(34)(56)}\\
% \end{tabular}
% \end{center}
%       The macro |\pmtprintorder| contains the standard printing order,
%       see \ref{uParameters}.
%
% \item |\pmtv|[|*|][\oarg{print order}]\marg{pmt}
%
%       prints a verbose form of the permutation.
%       The commands |\pmtvshorttrue| and |\pmtvshortfalse| controls whether
%       the package prints only the row of images or the full pre-image/image
%       format.
%
% \item |\pmttable|[|*|][\oarg{print order}]\marg{list of pmts}\marg{list of pmts}
% \item |\pmtvtable|[|*|][\oarg{print order}]\marg{list of pmts}\marg{list of pmts}
%
%       The commands compose each $\sigma_1$ of the first list with each
%       $\sigma_2$ of the second list and write the result
%       $\sigma_1\circ\sigma_2$ in row $\sigma_1$ and column $\sigma_2$.
%       For example,
% \begin{verbatim}
%    $$\pmttable{(),(12),(13),(23),(123),(132)}
%               {(),(12),(13),(23),(123),(132)}$$\end{verbatim}
%		creates
%           $$\pmttable{(),(12),(13),(23),(123),(132)}
%                      {(),(12),(13),(23),(123),(132)}$$
%       '()' stands for the identity map here.
%       \emph{Do not write} |\pmttable{,(12),...|. You may write
%           |\pmttable{(12),(123)}{(),(23),(123),(132)}|
%       to typeset a piece of the table or use |\pmtvtable| to print all
%       permutations verbose. The optional arguments effect all printed
%       permutations.
%
%       If you create really big tables like the one of $S_5$, you surely want
%       to cut the whole table in pieces and produce subtables on different
%       pages. This leads to alignment problems since the first column on the
%       first page need not to have the width of the first column on the second
%       page. Bad luck!
% \end{syntax}
% \medbreak
% Now we discuss how to calculate with the \textsf{permute} package.
% Let \meta{current pmt} denote the (internal) current permutation and
% \meta{name} another internal (stored) permutation.
% \begin{syntax}
% \item |\pmtload|\marg{name}\hphantom{mmmmmm}\qquad
%       \meta{current pmt} $\gets$ \meta{name}
%
% \item |\pmtsave|\marg{name}\hphantom{mmmmmm}\qquad
%       \meta{name} $\gets$ \meta{current pmt}
%
% \item |\pmtid|[\oarg{name}]\hphantom{\meta{pmt}\ttfamily mmmmmm}$\!$\qquad
%       \meta{current pmt} $\gets$ identity map
%
% \item |\pmtdo|[\oarg{name}]\marg{pmt}\hphantom{\ttfamily mmmm}$\!$\qquad
%       \meta{current pmt} $\gets$ \meta{pmt} $\circ$ \meta{current pmt}
%
% \item |\pmtcirc|[\oarg{name}]\marg{pmt}\hphantom{\ttfamily mm}$\!$\qquad
%       \meta{current pmt} $\gets$ \meta{current pmt} $\circ$ \meta{pmt}
%
% \item |\pmtprint|[|*|][\oarg{print order}]\hphantom{\ttfamily m}\qquad
%       prints \meta{current pmt}.
%
% \item |\pmtvprint|[|*|][\oarg{print order}]\qquad
%       prints \meta{current pmt}.
%
% \item |\pmtimageof|[\oarg{name}]\marg{pre-image}
%
%       prints image of \meta{pre-image} under \meta{current pmt}.
%
% \item |\pmtpreimageof|[\oarg{name}]\marg{image}
%
%       prints pre-image of \meta{image} under \meta{current pmt}.
% \end{syntax}
% If you use any optional \oarg{name}, this permutation replaces
% \meta{current pmt}.
% For example, |\pmtid[a]| makes the permutation $a$ to be the identity map
% or |\pmtdo[a]|\marg{pmt} performs $a$ $\gets$ \meta{pmt} $\circ$ $a$.
%
% \medbreak
% Finally examples which all print the result of
% $\pmtv[1\ldots kl\ldots n]{1{f(1)} \ldots\ldots k{f(k)} l{f(l)}^^A
%                                    \ldots\ldots n{f(n)}}\circ \pmt{(kl)}$,
% namely
% \pmtid\pmtdo{(kl)}\pmtdo{1{f(1)} k{f(k)} l{f(l)} n{f(n)}}
% \pmtvprint[1\ldots kl\ldots n].
% \begin{verbatim}
%   \pmtid
%   \pmtdo{1{f(1)} \ldots\ldots k{f(k)} l{f(l)} \ldots\ldots n{f(n)}}
%   \pmtcirc{(kl)}
%   \pmtvprint[1\ldots kl\ldots n]
%
%   \pmtid
%   \pmtdo{(kl)}
%   \pmtdo{1{f(1)} k{f(k)} l{f(l)} n{f(n)}}
%   \pmtvprint[1\ldots kl\ldots n]\end{verbatim}
% We can drop the two |\ldots| pairs (also in the first example) since image
% and pre-image are equal.
%
%
% \subsection{Parameters}\label{uParameters}
%
% \begin{syntax}
% \item |\pmtprintorder|
%
%       contains the standard printing order which is used whenever you leave
%       out or forget the optional \meta{print order} argument. By default it
%       contains the sequence |123456789abcdefghi|. You may adjust it to your
%       needs, for example, |\renewcommand*\pmtprintorder{123456}| if you work
%       with $S_6$. This is especially good if you use the verbose printing
%       format. You can forget the optional \meta{print order} in this case:
% \begin{center}
% \renewcommand*\pmtprintorder{123456}
% \begin{tabular}{@{}ll@{}}
% |\renewcommand*\pmtprintorder{123456}|\\
% |\pmtv{()}|&prints \pmtv{()}\\  \noalign{\medskip}
% |\pmtv{(123)}|&prints \pmtv{(123)}\\ \noalign{\medskip}
% |\pmtv{(12)(23)(16)(34)(45)}|&prints \pmtv{(12)(23)(16)(34)(45)}
% \end{tabular}
% \end{center}
%
% \item |\pmtseparator|
%
%       contains the separator used for the optional star. By default it is a
%       space: |\newcommand*\pmtseparator{ }|. Since it's not a backslashed
%       space |\|\textvisiblespace, it is ignored in math mode, in particular
%       in the verbose output format. But you may write
%       |\renewcommand*\pmtseparator{\ }|.
%
% \item |\pmtidname|
%
%       contains the string which is printed in the cycle based format
%       if a permutation is the identity map. It is predefined via
%       |\newcommand*\pmtidname{id}|.
%
% \item |\pmtldelim|
% \item |\pmtrdelim|
%
%       contain the left respectively right delimiter for the verbose format.
%       |\left(| and |\right)| are used by default.
%
% \item |\pmttableborders|
%
%       contains |lt| which makes a left border column and a top border line.
%       You may redefine it to be empty or to contain |l|, |t|, |lt| or |tl|.
%
% \item |\pmtarraystretch|
%
%       contains |2| and is used as |\arraystretch| for the table. You may
%       write |\renewcommand*\pmtarraystretch{1.3}| and get more compact
%       tables:
%			$$\def\pmtarraystretch{1.3}
%			  \pmttable{(),(12),(23)}{(),(12),(23)}$$
% \end{syntax}
%
%
% \StopEventually{}
%
%
% \CheckSum{717}
%
%
% \section{Implementation} 
%
%
% \subsection{General concept}
%
% Permutations, pre-images, and images are stored in macros. In the sequel we
% use, for example, \meta{image} for an argument which must be a macro and
% \marg{image} if the image is required explicitly. We define the following
% internal commands, which make the definition of the user commands easier.
%
% \begin{syntax}
% \item |\pmt@GetImageOf|\marg{pre-image}\meta{pmt}
%
%       Defines |\pmt@preimage|, its image |\pmt@image|, and \emph{removes} the
%       pre-image/image pair from \meta{pmt}. |\pmt@iffound| equals |\iffalse|
%       if and only if the pair couldn't be removed (since never existent).
%
% \item |\pmt@GetPreimageOf|\marg{image}\meta{pmt}
%
%       Defines |\pmt@image|, its pre-image |\pmt@preimage|, and leaves
%       \meta{pmt} \emph{unchanged}. |\pmt@iffound| equals |\iffalse|
%       if and only if such pair is not found.
%
% \item |\pmt@Whirl|\meta{a}\meta{b}\meta{c}
%
%       \meta{a} $\gets$ \meta{b} $\circ$ \meta{c}.
%       Note that \meta{c} must not equal |\pmt@b|.
%
% \item |\pmt@GetPmt|\meta{macro}\marg{pmt}
%
%       The cycle/verbose input format is converted to the internal data
%       format and assigned to \meta{macro}.
%
% \item |\pmt@PrintPmt|\meta{pmt}\qquad and\qquad |\pmt@PrintVPmt|\meta{pmt}
%
%       print the permutation (verbose) with respect to |\pmt@order|.
%       \emph{Both destroy} |\pmt@a|,\ldots,|\pmt@c|, |\pmt@image|,
%       \emph{and so on.}
% \end{syntax}
%
%
% \subsection{Preliminaries}
%
% \begingroup
%    \begin{macrocode}
%<*package>
\ProvidesPackage{permute}[1999/11/10 v0.12 (aeio)(cdt)(knm)]
%    \end{macrocode}
% I still wonder whether someone finds out what |(aeio)(cdt)(knm)| means.
% \vskip\lineskip
% \endgroup
%
% \begin{macro}{\pmt@iffirst}
% \begin{macro}{\pmt@iffound}
% \begin{macro}{\pmt@ifsep}
% are each controlled by two simple definitions.
%    \begin{macrocode}
\def\pmt@firsttrue{\let\pmt@iffirst\iftrue}
\def\pmt@firstfalse{\let\pmt@iffirst\iffalse}
%    \end{macrocode}
%    \begin{macrocode}
\def\pmt@foundtrue{\let\pmt@iffound\iftrue}
\def\pmt@foundfalse{\let\pmt@iffound\iffalse}
%    \end{macrocode}
%    \begin{macrocode}
\def\pmt@septrue{\let\pmt@ifsep\iftrue}
\def\pmt@sepfalse{\let\pmt@ifsep\iffalse}
%    \end{macrocode}
% \end{macro}\end{macro}\end{macro}
%
%
% \subsection{The data format}
%
% We store a permutation as a list of pre-image/image pairs, but we drop all
% with pre-image=image, e.g.\ |{1}{2}{2}{3}{3}{1}| represents (123) no matter
% whether considered as element of $S_3$, $S_4$ or $S_6$.
% The identity map is represented by an empty macro.
%
% \begin{macro}{\pmt@GetPreimageOf}
% We define the image and get its pre-image from a submacro. |\pmt@firsttrue|
% indicates that we are looking for the first of pre-image/image.
%    \begin{macrocode}
\def\pmt@GetPreimageOf#1#2{%
    \def\pmt@image{#1}\pmt@firsttrue
    \expandafter\pmt@GIO@#2\relax\relax}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pmt@GetImageOf}
% We assign the pre-image, empty |\pmt@gio| (which holds the rest of |#2|), get
% the image, and assign the rest of the permutation to |#2|. |\pmt@firstfalse|
% indicates that we are looking for the second of pre-image/image.
%    \begin{macrocode}
\def\pmt@GetImageOf#1#2{%
    \def\pmt@preimage{#1}\let\pmt@gio\@empty \pmt@firstfalse
    \expandafter\pmt@GIO@#2\relax\relax
    \let#2\pmt@gio}
%    \end{macrocode}
% Now we iterate down the list. |\pmt@image| or |\pmt@preimage| is used as
% temporary macro. If we have found the correct (pre-)image, we can define it
% and get the rest of the permutation (up to |\relax\relax|).
%    \begin{macrocode}
\def\pmt@GIO@#1#2{%
    \pmt@iffirst \def\pmt@preimage{#2}\else
                 \def\pmt@image{#1}\fi
    \ifx\pmt@image\pmt@preimage
        \def\pmt@preimage{#1}\def\pmt@image{#2}\pmt@foundtrue
        \expandafter\pmt@GIO@@
    \else
%    \end{macrocode}
% If we haven't found the correct (pre-)image: Image and pre-image must be
% equal if we have reached the end of list; otherwise we probably extend
% |\pmt@gio| and continue the loop.
%    \begin{macrocode}
        \ifx\relax#2%
            \pmt@foundfalse
            \pmt@iffirst \let\pmt@preimage\pmt@image
                   \else \let\pmt@image\pmt@preimage \fi
            \expandafter\@gobbletwo
        \else
            \pmt@iffirst\else \pmt@AddTo\pmt@gio{{#1}{#2}}\fi
        \fi
        \expandafter\pmt@GIO@
    \fi}
%    \end{macrocode}
% The following macro gets the rest of permutation.
%    \begin{macrocode}
\def\pmt@GIO@@#1\relax\relax{%
    \pmt@iffirst\else \pmt@AddTo\pmt@gio{#1}\fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pmt@AddTo}
% \begin{macro}{\pmt@Extend}
% |\pmt@AddTo| adds |#2| to the contents of the macro |#1|.
% |\pmt@Extend| expands the first token of |#2| before doing the same.
%    \begin{macrocode}
\def\pmt@AddTo#1#2{\expandafter\def\expandafter#1\expandafter{#1#2}}
\def\pmt@Extend#1#2{%
    \expandafter\pmt@AddTo\expandafter#1\expandafter{#2}}
%    \end{macrocode}
% \end{macro}\end{macro}
%
%
% \subsection{Whirling things round}\label{iWhirlingThingsRound}
%
% \begin{macro}{\pmt@Whirl}
% Init, whirl, assign.
%    \begin{macrocode}
\def\pmt@Whirl#1#2#3{%
    \let\pmt@b#2\let\pmt@c#3\let\pmt@a\@empty
    \pmt@Whirl@
    \let#1\pmt@a}
%    \end{macrocode}
% If |\pmt@c| is empty, we only need to append the contents of |\pmt@b| to
% |\pmt@a| since |\pmt@c| represents the identity map.
%    \begin{macrocode}
\def\pmt@Whirl@{%
    \ifx\pmt@c\@empty
        \pmt@Extend\pmt@a\pmt@b
    \else
%    \end{macrocode}
% Otherwise we append the first pre-image and its image under the composition,
% and continue to check whether |\pmt@c| is empty.
%    \begin{macrocode}
        \expandafter\pmt@Whirl@@\pmt@c\relax
        \expandafter\pmt@Whirl@
    \fi}
%    \end{macrocode}
% |\pmt@c| becomes shorter, we get the `composed' image, \ldots
%    \begin{macrocode}
\def\pmt@Whirl@@#1#2#3\relax{%
    \def\pmt@first{#1}\def\pmt@c{#3}%
    \pmt@GetImageOf{#2}\pmt@b
%    \end{macrocode}
% and append the new pre-image/image pair if first$\neq$image.
% There is only some trouble in making braces around the (pre-)image.
%    \begin{macrocode}
    \ifx\pmt@first\pmt@image\else
        \def\pmt@first{{#1}}%
        \pmt@Extend\pmt@first{\expandafter{\pmt@image}}%
        \pmt@Extend\pmt@a\pmt@first
    \fi}
%    \end{macrocode}
% \end{macro}
%
%
% \subsection{Getting input}
%
% \begin{macro}{\pmt@InputError}
% gives an error message.
%    \begin{macrocode}
\def\pmt@InputError#1{\PackageError{Permute}{#1}\@ehd}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pmt@GetPmt}
% We initialize |\pmt@a|, do the conversion and assign the result to |#1|.
%    \begin{macrocode}
\def\pmt@GetPmt#1#2{%
    \def\pmt@a{#2}%
    \pmt@foundtrue \pmt@firstfalse
    \@ifnextchar({\let\pmt@a\@empty \pmt@GetCPmt}%
                 \pmt@GetVPmt
    #2\relax\relax
    \let#1\pmt@a}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pmt@GetVPmt}
% For the verbose format we only test for an even number of arguments.
%    \begin{macrocode}
\def\pmt@GetVPmt#1#2{%
    \ifx\relax#2%
        \ifx\relax#1\else
            \pmt@InputError{Odd number of tokens}%
            \let\pmt@a\@empty
        \fi
    \else
        \expandafter\pmt@GetVPmt
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pmt@GetCPmt}
% is called |\pmt@GetCPmt|\meta{cycles}|\relax| and |\pmt@a| becomes |\pmt@a|
% $\circ$ \meta{cycles}. If we haven't found a right parenthesis and reach the
% end of the cycles, we give an error message. Reaching |\relax| we terminate
% the loop by gobbling a far away |\pmt@GetCPmt|.
%    \begin{macrocode}
\def\pmt@GetCPmt#1{%
    \ifx#1\relax
        \pmt@iffound\else \pmt@InputError{Missing `)'}\fi
        \expandafter\@gobble
    \else
%    \end{macrocode}
% If we find a right parenthesis, we either give an error message or use the
% first element of the current cycle as image of the last element. In this case
% we compose |\pmt@a| and |\pmt@c| via |\pmt@Whirl| defined in section
% \ref{iWhirlingThingsRound}.
%    \begin{macrocode}
        \ifx#1)%
            \pmt@iffound
                \pmt@InputError{Extra `)'}%
            \else
                \pmt@iffirst\else
                    \pmt@Extend\pmt@c\pmt@first
                    \pmt@Whirl\pmt@a\pmt@a\pmt@c
                \fi
                \pmt@foundtrue
            \fi
        \else
%    \end{macrocode}
% A left parenthesis might lead to an error, but in any case initializes two
% \texttt{if}s.
%    \begin{macrocode}
        \ifx#1(%
            \pmt@iffound\else
                \pmt@InputError{Extra `(' or missing `)'}%
            \fi
            \pmt@firsttrue \pmt@foundfalse
        \else
%    \end{macrocode}
% Now we handle all other tokens. If we are outside a cycle (i.e.\ a closing
% parenthesis has been found), we give an error message.
%    \begin{macrocode}
        \pmt@iffound
            \pmt@InputError{Missing `('}%
        \else
%    \end{macrocode}
% Otherwise we initialize or extend |\pmt@c|.
%    \begin{macrocode}
            \pmt@iffirst
                \pmt@firstfalse \def\pmt@first{{#1}}\def\pmt@c{{#1}}%
            \else
                \pmt@AddTo\pmt@c{{#1}{#1}}%
            \fi
        \fi\fi\fi
    \fi
%    \end{macrocode}
% Continue the loop (if not gobbled).
%    \begin{macrocode}
    \pmt@GetCPmt}
%    \end{macrocode}
% \end{macro}
%
%
% \subsection{Doing output}
%
% \begin{macro}{\pmt@PrintVPmt}
% Is easy.
%    \begin{macrocode}
\def\pmt@PrintVPmt#1{%
    \let\pmt@a#1\pmt@sepfalse
    \ensuremath{\pmtldelim
                \expandafter\pmt@PrintVPmt@\pmt@order\relax
                \pmtrdelim}}
%    \end{macrocode}
% While |\relax| is not reached, we define pre-image, get the image, and use
% |\atop| to typeset the pre-image/image pair.
%    \begin{macrocode}
\def\pmt@PrintVPmt@#1{%
    \ifx\relax#1\@empty \else
        \pmt@GetImageOf{#1}\pmt@a
        \pmt@ifsep \pmt@separator \else \pmt@septrue \fi
        \mkern1mu%
        \pmt@ifshort \pmt@image
               \else{\pmt@preimage\atop\pmt@image}\fi
        \mkern1mu%
        \expandafter\pmt@PrintVPmt@
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pmtshorttrue}
% \begin{macro}{\pmtshortfalse}
% The user accessible \texttt{if} used above.
%    \begin{macrocode}
\def\pmtshorttrue{\let\pmt@ifshort\iftrue}
\def\pmtshortfalse{\let\pmt@ifshort\iffalse}
\pmtshortfalse
%    \end{macrocode}
% \end{macro}\end{macro}
%
% \begin{macro}{\pmt@GetFirst}
% defines |\pmt@first| and gobbles all tokens up to the next |\relax|.
%    \begin{macrocode}
\def\pmt@GetFirst#1#2\relax{\def\pmt@first{#1}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pmt@PrintPmt}
% We print |\pmtidname| if necessary.
%    \begin{macrocode}
\def\pmt@PrintPmt#1{%
    \let\pmt@a#1%
    \ifx\pmt@a\@empty \pmtidname \else
        \expandafter\pmt@PrintPmt@\pmt@order\relax
    \fi}
%    \end{macrocode}
% While having an order, we define the first pre-image and print the cycle.
%    \begin{macrocode}
\def\pmt@PrintPmt@#1{%
    \ifx\relax#1\@empty
        \expandafter\pmt@PrintPmt@@
    \else
        \def\pmt@first{#1}\pmt@PrintCycle
        \expandafter\pmt@PrintPmt@
    \fi}
%    \end{macrocode}
% Having no order, we print the rest.
%    \begin{macrocode}
\def\pmt@PrintPmt@@{%
    \ifx\pmt@a\@empty\else
        \expandafter\pmt@GetFirst\pmt@a\relax
        \pmt@PrintCycle
        \expandafter\pmt@PrintPmt@@
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pmt@PrintCycle}
% We print the cycle containing (and beginning with) the contents of
% |\pmt@first| if it appears as pre-image.
%    \begin{macrocode}
\def\pmt@PrintCycle{%
    \expandafter\pmt@GetImageOf\expandafter{\pmt@first}\pmt@a
    \pmt@iffound
        (\pmt@preimage\pmt@separator\pmt@image
         \ifx\pmt@a\@empty\else \pmt@PrintCycle@\pmt@image \fi
        )%
    \fi}
%    \end{macrocode}
% While we haven't found the end of the cycle, \ldots
%    \begin{macrocode}
\def\pmt@PrintCycle@#1{%
    \expandafter\pmt@GetImageOf\expandafter{#1}\pmt@a
    \ifx\pmt@image\pmt@first\else
%    \end{macrocode}
% we print the image and use the image as new pre-image if permutation is
% not empty yet.
%    \begin{macrocode}
        \pmt@separator\pmt@image
        \ifx\pmt@a\@empty \expandafter\@gobblefour \fi
        \expandafter\pmt@PrintCycle@\expandafter\pmt@image
    \fi}
%    \end{macrocode}
% \end{macro}
%
%
% \subsection{User commands and parameters}
%
% \begin{macro}{\pmtidname}
% \begin{macro}{\pmtprintorder}
% \begin{macro}{\pmtseparator}
% \begin{macro}{\pmtldelim}
% \begin{macro}{\pmtrdelim}
% \begin{macro}{\pmttableborders}
% \begin{macro}{\pmtarraystretch}
% Some predefined values.
%    \begin{macrocode}
\newcommand*\pmtidname{id}
\newcommand*\pmtprintorder{123456789abcdefghi}
\newcommand*\pmtseparator{ }
\newcommand*\pmtldelim{\left(}
\newcommand*\pmtrdelim{\right)}
\newcommand*\pmttableborders{lt}
\newcommand*\pmtarraystretch{2}
%    \end{macrocode}
% \end{macro}\end{macro}\end{macro}\end{macro}
% \end{macro}\end{macro}\end{macro}
%
% \begin{macro}{\pmt@GetPrintArgs}
% This helper executes |#1| after getting the optional printing arguments.
%    \begin{macrocode}
\def\pmt@GetPrintArgs#1{%
    \let\pmt@order\pmtprintorder \def\pmt@next{#1}%
    \@ifstar{\let\pmt@separator\pmtseparator \pmt@GPA@}%
            {\let\pmt@separator\@empty \pmt@GPA@}}
%    \end{macrocode}
% If there is no optional argument, we use |\pmtprintorder|, i.e.\ we don't
% redefine |\pmt@order|.
%    \begin{macrocode}
\def\pmt@GPA@{\@ifnextchar[\pmt@GPA@@\pmt@next}
\def\pmt@GPA@@[#1]{\def\pmt@order{#1}\pmt@next}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pmt}
% \begin{macro}{\pmtv}
% \begin{macro}{\pmtprint}
% \begin{macro}{\pmtvprint}
% The first user commands in terms of known definitions.
%    \begin{macrocode}
\newcommand*\pmt {\pmt@GetPrintArgs{\pmt@\pmt@PrintPmt}}
\newcommand*\pmtv{\pmt@GetPrintArgs{\pmt@\pmt@PrintVPmt}}
\def\pmt@#1#2{\pmt@GetPmt\pmt@a{#2}#1\pmt@a}
%    \end{macrocode}
%    \begin{macrocode}
\newcommand*\pmtprint {\pmt@GetPrintArgs{\pmt@PrintPmt\pmt@curr}}
\newcommand*\pmtvprint{\pmt@GetPrintArgs{\pmt@PrintVPmt\pmt@curr}}
%    \end{macrocode}
% \end{macro}\end{macro}\end{macro}\end{macro}
%
% \begin{macro}{\pmt@OptName}
% `executes' |#1| with argument |\pmt@curr| \ldots
%    \begin{macrocode}
\def\pmt@OptName#1{\def\pmt@next##1{#1}%
    \@ifnextchar[\pmt@OptName@{\pmt@next\pmt@curr}}
%    \end{macrocode}
% or |\pmt@s@|\meta{name} if an optional argument is given. |\pmt@LoadPmt|
% ensures that the permuation |#1|$=$\meta{name} is defined.
%    \begin{macrocode}
\def\pmt@OptName@[#1]{%
    \pmt@LoadPmt{#1}\pmt@a
    \expandafter\pmt@next\csname pmt@s@#1\endcsname}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pmt@LoadPmt}
% loads the permutation with name |#1| to |#2|.
%    \begin{macrocode}
\def\pmt@LoadPmt#1#2{%
    \@ifundefined{pmt@s@#1}%
        {\expandafter\let\csname pmt@s@#1\endcsname\@empty}
    \expandafter\let\expandafter#2\csname pmt@s@#1\endcsname}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pmtsave}
% \begin{macro}{\pmtload}
% \begin{macro}{\pmtid}
% Some more user commands.
%    \begin{macrocode}
\def\pmtsave#1{\expandafter\let\csname pmt@s@#1\endcsname\pmt@curr}
\def\pmtload#1{\pmt@LoadPmt{#1}\pmt@curr}
%    \end{macrocode}
% |##1| $\in$ \{|\pmt@curr|,|\pmt@s@|\meta{name}\} becomes empty.
%    \begin{macrocode}
\newcommand*\pmtid{\pmt@OptName{\let##1\@empty \ignorespaces}}
\pmtid
%    \end{macrocode}
% \end{macro}\end{macro}\end{macro}
%
% \begin{macro}{\pmtdo}
% \begin{macro}{\pmtcirc}
% The only difference here is the order of |\pmt@a| and |##1|.
%    \begin{macrocode}
\newcommand*\pmtdo{\pmt@OptName{\pmtdo@##1\pmt@a##1}}
\newcommand*\pmtcirc{\pmt@OptName{\pmtdo@##1##1\pmt@a}}
\def\pmtdo@#1#2#3#4{\pmt@GetPmt\pmt@a{#4}\pmt@Whirl#1#2#3\ignorespaces}
%    \end{macrocode}
% \end{macro}\end{macro}
%
% \begin{macro}{\pmtimageof}
% \begin{macro}{\pmtpreimageof}
% We use different arguments to the submacro to get and print the (pre-)image.
%    \begin{macrocode}
\newcommand*\pmtimageof{\pmtimageof@\pmt@GetImageOf\pmt@image}
\newcommand*\pmtpreimageof{\pmtimageof@\pmt@GetPreimageOf\pmt@preimage}
%    \end{macrocode}
%    \begin{macrocode}
\def\pmtimageof@#1#2{%
    \@ifnextchar[{\pmtimageof@@#1#2}{\pmtimageof@@#1#2[]}}
\def\pmtimageof@#1#2[#3]#4{%
     \ifx\@empty#3\@empty
         \let\pmt@a\pmt@curr
     \else
         \pmt@LoadPmt{#3}\pmt@a
     \fi
     #1{#4}\pmt@a
     #2}
%    \end{macrocode}
% TODO: These two user macros don't behave like |\pmtid|, |\pmtdo|, and so on.
% An empty named permutation \meta{name} leads here to \meta{current pmt} and not
% to |\pmt@s@|\meta{name}.
% \end{macro}\end{macro}
%
%
% \subsection{Making tables}
%
% \begin{macro}{\pmtvtable}
% We use appropriate local redefinitions of |\pmtprint|.
%    \begin{macrocode}
\newcommand*\pmttable
    {\begingroup
     \def\pmtprint{\let\pmt@order\pmt@porder\pmt@PrintPmt\pmt@curr}%
     \pmt@GetPrintArgs\pmt@PrintTable}
%    \end{macrocode}
%    \begin{macrocode}
\newcommand*\pmtvtable
    {\begingroup
     \def\pmtprint{\let\pmt@order\pmt@porder\pmt@PrintVPmt\pmt@curr}%
     \pmt@GetPrintArgs\pmt@PrintTable}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pmt@PrintTable}
% We use macros defined below to indicate the desired borders.
%    \begin{macrocode}
\def\pmt@PrintTable#1#2{%
    \let\pmt@ifleft\iffalse
    \pmt@topfalse
    \expandafter\pmt@SetBorders\pmttableborders\relax
%    \end{macrocode}
%    \begin{macrocode}
    \let\pmt@porder\pmt@order
    \let\arraystretch\pmtarraystretch
%    \end{macrocode}
% Determine how many columns the table will have, and choose the right
% tabular call (according to the desired left border)
%    \begin{macrocode}
    \@tempcnta\z@ \pmt@for{\advance\@tempcnta\@ne}{#2}%
%    \end{macrocode}
% Note: It's possible to write |\begin{tabular}{\pmt@ifleft c|\ldots, but the
% construction here is independent of that.
%    \begin{macrocode}
    \edef\pmt@next{%
        \noexpand\begin{tabular}{\pmt@ifleft c|\else p{\z@}@{}\fi
            *{\the\@tempcnta}{@{\ }c@{\ }}}}%
    \pmt@next
%    \end{macrocode}
% Print the top border if desired.
%    \begin{macrocode}
    \pmt@iftop
        \pmt@ifleft \ensuremath{\circ}\fi
        \pmt@for{&\pmtid\pmtdo{##1}\pmtprint}{#1}%
        \\ \hline
    \fi
%    \end{macrocode}
% And process the rest of the table: we end the previous tabular line (if there
% is any), print the left border (if desired) and print one line of the table.
%    \begin{macrocode}
    \gdef\pmt@topperms{#2}\pmt@toptrue
    \pmt@for{%
        \pmt@iftop \pmt@topfalse \else \expandafter\\\fi
        \pmt@ifleft \pmtid\pmtdo{##1}\pmtprint \fi
        \pmt@PrintTableLine{##1}}%
    {#1}%
    \end{tabular}\endgroup}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pmt@PrintTableLine}
% is |\pmt@PrintTableLine@{#1}|$\langle$\textit{expansion of}
% |\pmt@topperms|$\rangle$|,\relax,|
%    \begin{macrocode}
\def\pmt@PrintTableLine#1{%
    \def\pmt@next{\pmt@PrintTableLine@{#1}}%
    \expandafter\pmt@next\pmt@topperms,\relax,}
%    \end{macrocode}
% Now we get |#1| and (step by step) each permutation of |\pmt@topperms|,
% and print the composition.
%    \begin{macrocode}
\def\pmt@PrintTableLine@#1#2,{%
    \ifx\relax#2\else
        \def\pmt@next{&\pmtid\pmtdo{#2}\pmtdo{#1}\pmtprint
                      \pmt@PrintTableLine@{#1}}%
        \expandafter\pmt@next
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pmt@for}
% performs |#1| for each element of the comma separated list |#2|.
%    \begin{macrocode}
\def\pmt@for#1#2{%
    \gdef\pmt@for@##1,{%
        \ifx\relax##1\else
            \def\pmt@next{#1\expandafter\pmt@for@}%
            \expandafter\pmt@next
        \fi}%
    \pmt@for@#2,\relax,}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pmt@SetBorders}
% \begin{macro}{\pmt@topfalse}
% \begin{macro}{\pmt@toptrue}
% \begin{macro}{\pmt@lefttrue}
% Get characters up to |\relax| and set \texttt{if}s.
%    \begin{macrocode}
\def\pmt@SetBorders#1{%
    \ifx\relax#1\else
        \if l#1\pmt@lefttrue \fi
        \if t#1\pmt@toptrue \fi
        \expandafter\pmt@SetBorders
    \fi}
%    \end{macrocode}
%    \begin{macrocode}
\def\pmt@topfalse{\global\let\pmt@iftop\iffalse}
\def\pmt@toptrue{\global\let\pmt@iftop\iftrue}
\def\pmt@lefttrue{\let\pmt@ifleft\iftrue}
%    \end{macrocode}
% \end{macro}\end{macro}\end{macro}\end{macro}
%
% \begingroup
%    \begin{macrocode}
%</package>
%    \end{macrocode}
% \endgroup
%
%
% \subsection{To do}
%
% It would be nice to have commands |\pmtpartialtable| and |\pmtvpartialtable|
% which print a specified part of a whole table. If requested, these commands
% should determine the width of the columns such that the columns are aligned
% correctly if all parts are printed and put together. For this procedure it
% would be convenient either to store the lists of permutations so that the
% commands can access them, or to let the package take control and print the
% table on different pages (if necessary).
%
% Cycle substitution: After |\pmtsubstitute{(123)(45)}{a}| the permutation
% (123)(45) is replaced by $a$ in the output. Difficult to implement (due to
% \meta{print order} and |\pmtprintorder|) and even more difficult if this
% substitution should take place `inside' permutations.
% In general, the latter is not possible or not reasonable.
% But it is interesting in context with the next ``to do'' paragraph.
%
% Implement possibility to print (and store) permutations as they have been
% entered.
% This does not mean just to store the character sequence since composition
% with other permutations must be possible, of course.
% The internal data format (or an additional list) must represent the input.
% Storing an additional \meta{print order} is not sufficient.
% For example, (123)(321) is represented by an empty string, but we cannot
% recreate it from the empty string and \meta{print order}.
% Thus we might need two additional data: \meta{print order} and something
% like the original string.
%
% New command |\pmtinverse|[\oarg{name}] (easy) and its applications.
%
%
% \subsection{History}
%
% \renewcommand\labelitemi{--}
% \begin{itemize}
% \item[0.1] from 1997/11/08 (unpublished)
%	\item commands |\pmt|, |\pmtloadid| (became |\pmtid|), |\pmtdo| (became
%         |\pmtcirc|), |\pmtprint| and |\pmttable| support $S_1,\ldots,S_9$
% \item[0.11] from 1998/12/17
%   \item restriction to $S_1,\ldots,S_9$ dropped
%	\item new commands |\pmtv|, |\pmtvprint|, |\pmtvtable| provide verbose
%         printing format and the old commands |\pmt|, |\pmtv|, |\pmtdo|,
%         |\pmtcirc|, |\pmttable| and |\pmtvtable| now accept verbose input
%   \item |\pmtprintorder|, |\pmtseparator|, |\pmtidname|, |\pmtldelim|,
%         |\pmtrdelim|, |\pmttableborders| (prior optional argument),
%         |\pmtarraystretch| are new parameters
% \item[0.12] from 1999/11/10
%   \item new commands |\pmtvshorttrue|, |\pmtvshortfalse|, |\pmtsave|,
%         |\pmtload|, |\pmtimageof| and |\pmtpreimageof|
%   \item enhanced commands |\pmtid|, |\pmtdo| and |\pmtcirc|
% \end{itemize}
%
%
% \Finale
%
\endinput