%% for a long time these were red and blue by default, %% now black, but keep variables to overwrite \definecolor{FuncColor}{rgb}{0.0,0.0,0.0} %% strange name because of pdflatex bug: \definecolor{Chapter }{rgb}{0.0,0.0,0.0} \definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064}
% write page numbers to a .pnr log file for online help \newwrite\pagenrlog \immediate\openout\pagenrlog =\jobname.pnr \immediate\write\pagenrlog{PAGENRS := [} \newcommand{\logpage}[1]{\protect\write\pagenrlog{#1, \thepage,}} %% were never documented, give conflicts with some additional packages
\newcommand{\GAP}{\textsf{GAP}}
%% nicer description environments, allows long labels \usepackage{enumitem} \setdescription{style=nextline}
\newpage\setcounter{page}{2}
{\small \section*{Copyright} \logpage{[ 0, 0, 1 ]}
{\copyright} by Christopher Jefferson \mbox{}}\\[1cm] \newpage
\def\contentsname{Contents\logpage{[ 0, 0, 2 ]}}
\tableofcontents \newpage
\chapter{\textcolor{Chapter }{The Ferret Package}}\label{The Ferret Package} \logpage{[ 1, 0, 0 ]} \hyperdef{L}{X84F30BD780680D41}{}
{ \index{Ferret package} This chapter describes the \textsf{GAP} package Ferret. Ferret implements highly efficient implementations of a range
of search algorithms on permutation groups. If you are interested in if Ferret
can be applied to another problem, please contact the authors, who will be
happy to look into if your problem can be solved with Ferret. \section{\textcolor{Chapter }{Replacing Built\texttt{\symbol{45}}in functionality}}\label{Replacing Built-in functionality} \logpage{[ 1, 1, 0 ]} \hyperdef{L}{X862CDAE07EF5953E}{}
{
Ferret automatically installs methods which replace GAP's a number of GAP's
built\texttt{\symbol{45}}in functionality: \begin{itemize} \item\emph{Intersection} for a list of permutation groups. \item\emph{Stabilizer(G,S,Action)} for a permutation group G, and the actions: \begin{itemize} \item\texttt{OnSets} \item\texttt{OnOnSets} \item\texttt{OnSetsDisjointSets} \item\texttt{OnSetsSets} \item\texttt{OnTuples} \item\texttt{OnPairs} \item\texttt{OnDirectedGraph} \end{itemize}
\item\emph{Stabilizer(G, S)} for a permutation group G and a: \begin{itemize} \item permutation \item transformation \item partial permutation \end{itemize}
\end{itemize}
If you would like to disable this functionality, you can use \ref{EnableFerretOverloads}.
if \mbox{\texttt{\mdseries\slshape active}} (a bool) is true, then enable Ferret specialisations of Intersection and
Stabilizer. Call with \mbox{\texttt{\mdseries\slshape active}} false to disable. }
Return if Ferret specialisations of Intersection and Stabilizer are currently
enabled. }
}
\section{\textcolor{Chapter }{Using 'Solve' to solve problems directly}}\label{Using 'Solve' to solve problems directly} \logpage{[ 1, 2, 0 ]} \hyperdef{L}{X856996FA785737BC}{}
{
The main method of using Ferret's functionality is the \texttt{Solve} (\ref{Solve}) method. This method intersects a list of permutation groups. The unusual
feature is that these permutation groups can be represented in a variety of
ways. They can be usual GAP permutation groups given as a list of generators,
or they can be the group which is the stabilizer of combinatorial object under
some action. Larger problems are then composed from these pieces. For example,
the stabilizer of a set S under a group G can be expressed as the intersection
of the group which stabilizes the set S and the group G. For this problem,
there would be no point using \texttt{Solve} (\ref{Solve}), as GAP's built in 'Stabilizer' function provides the same functionality.
However, with \texttt{Solve} (\ref{Solve}) we can intersect any number of groups at the same time, for example finding
the intersection of two groups G and H, the stabilizer of a set S and the
stabilizer of a set of sets T, with the following code: \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@Solve([ConInGroup(G), ConInGroup(H), |
!gapprompt@>| !gapinput@ConStabilize(S, OnSets), ConStabilize(T, OnSetSets)])| \end{Verbatim}
The currently allowed arguments to \texttt{Solve} (\ref{Solve}) are: \begin{itemize} \item\texttt{ConInGroup} (\ref{ConInGroup}), which represents a Permutation Group in GAP \item\texttt{ConStabilize} (\ref{ConStabilize:for an object and an action}), which takes an object and an action. \end{itemize}
}
}
\chapter{\textcolor{Chapter }{The Solve Method}}\label{SolveChapter} \logpage{[ 2, 0, 0 ]} \hyperdef{L}{X83B607B385FBB68A}{}
{
The central functionality of the Ferret package is based around the Solve
method. This function performs a backtrack search, using the permutation
backtracking algorithm, over a set of groups or cosets. Often users will want
to use a higher level function which wraps this functionality, such as \texttt{Stabilizer} or \texttt{Intersection}. The solve function accepts a list of groups, and finds their intersection.
For efficiency reasons, these groups can be specified in a variety of
different ways. As an example, we will consider how to implement \texttt{Stabilizer(G, S, OnSets)}, the stabilizer of a set S in a permutation group G using Solve (this is not
necessary, as when Ferret is loaded this method is replaced with a
Ferret\texttt{\symbol{45}}based implementation). Another way of viewing \texttt{Stabilizer(G, S, OnSets)} is as the intersection of G with \texttt{Stabilizer(Sym(n), S, OnSets)}, where $Sym(n)$ is the symmetric group on n points, and n is at least as large as the largest
moved point in G. Solve takes a list of objects which represent groups. Two of
these are \texttt{ConInGroup(G)}, which represents the group G, and \texttt{ConStabilize(S, OnSets)}, which represents the group which stabilizes S. We find the intersection of
these two groups by \texttt{Solve([ConInGroup(G), ConStabilize(S, OnSets)])}. \section{\textcolor{Chapter }{Methods of representing groups in Ferret}}\label{Representing groups in Ferret} \logpage{[ 2, 1, 0 ]} \hyperdef{L}{X7ADF81FD7F1709BB}{}
{
Groups and cosets must be represented in a way which Ferret can understand.
The following list gives all the types of groups which Ferret accepts, and how
to construct them.
\subsection{\textcolor{Chapter }{ConStabilize (for an object and an action)}} \logpage{[ 2, 1, 1 ]}\nobreak \hyperdef{L}{X780A9D5A7F85ADD6}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ConStabilize({\mdseries\slshape object, action})\index{ConStabilize@\texttt{ConStabilize}!for an object and an action} \label{ConStabilize:for an object and an action}
}\hfill{\scriptsize (function)}}\\ \noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ConStabilize({\mdseries\slshape object, n})\index{ConStabilize@\texttt{ConStabilize}!for a transformation or partial perm} \label{ConStabilize:for a transformation or partial perm}
}\hfill{\scriptsize (function)}}\\
This function creates a Constraint which can be given to \texttt{Solve} (\ref{Solve}). It does not perform any useful actions by itself
In the first form this represents the group which stabilises \mbox{\texttt{\mdseries\slshape object}} under \mbox{\texttt{\mdseries\slshape action}}. The currently allowed actions are \texttt{OnSets}, \texttt{OnSetsSets}, \texttt{OnSetsDisjointSets}, \texttt{OnSetsTuples}, \texttt{OnTuples}, \texttt{OnPairs} and \texttt{OnDirectedGraph}.
In the second form it represents the stabilizer of a partial perm or
transformation in the symmetric group on \mbox{\texttt{\mdseries\slshape n}} points. }
Finds the intersection of the list \mbox{\texttt{\mdseries\slshape Constraints}}. Each member of \mbox{\texttt{\mdseries\slshape constraints}} should be a group or coset generated by one of \texttt{ConInGroup} (\ref{ConInGroup}) or \texttt{ConStabilize} (\ref{ConStabilize:for an object and an action}). The optional second argument allows configuration options to be passed in.
These follow options are supported: \begin{description} \item[{\texttt{rbaseCellHeuristic} (default "smallest")}] The cell to be branched on. This is the option which will most effect the time
taken to search. the default is usually best. Other options are: "First"
(first cell), "Largest" (largest cell), "smallest2" (the 2nd smallest cell), "random" (a random cell) and "randomsmallest" (one of the smallest cells,
chosen randomly) \item[{\texttt{rbaseValueHeuristic} (default "smallest")}] Choose which cell to branch on within a cell. While this will generally make a
big difference to search, it is hard to predict the best value, and small
changes to the problem will change the best heuristic. Options are the same as \texttt{rbaseCellHeuristic}. \item[{\texttt{searchValueHeuristic} (default \texttt{RBase})}] The order to branch during search. In general the best order is very hard to
predict. Options are "RBase", "InvRBase", "Random", "Sorted" or "Nosort"
(which uses the order the values naturally end up in by the algorithm). \item[{\texttt{searchFirstBranchValueHeuristic} (default \texttt{RBase})}] Choose the search order used just on the left\texttt{\symbol{45}}most branches
of search. Allows the same options as \texttt{searchValueHeuristic} \item[{\texttt{stats} (default \texttt{false})}] Change the return value to provide a range of information about how search
performed (implies \texttt{recreturn}). This information will change between releases. \item[{\texttt{nodeLimit} (default \texttt{false}) }] Either \textsc{false}, or an integer which places a limit on the amount of search which should be
performed. WARNING: When this option is set to an integer, Ferret will return
the current best answer when the limit is reached, which may be a subgroup of
the actual result. To know if this limit was reached, set \texttt{stats} to \textsc{true}, and check the nodes. \item[{\texttt{recreturn} (default \texttt{false}) }] Return a record containing private information, rather than the group. \item[{\texttt{only{\textunderscore}find{\textunderscore}generators} (default \texttt{true})}] By default only find the generators of the group. If false, then find all
members of the group. This option is only useful for testing. If 'true', then
sets 'recreturn' to true. \end{description}
}
}
}
\chapter{\textcolor{Chapter }{Installing and Loading the Ferret Package}}\label{Installing and Loading the Ferret Package} \logpage{[ 3, 0, 0 ]} \hyperdef{L}{X782C0DD47E1D28EF}{}
{
\section{\textcolor{Chapter }{Unpacking the Ferret Package}}\label{Unpacking the Ferret Package} \logpage{[ 3, 1, 0 ]} \hyperdef{L}{X8527DE187ADA7D7A}{}
{
If the Ferret package was obtained as a part of the \textsf{GAP} distribution from the ``Download'' section of the \textsf{GAP} website, you may proceed to Section \ref{Compiling Binaries of the Ferret Package}. Alternatively, the Ferret package may be installed using a separate archive,
for example, for an update or an installation in a
non\texttt{\symbol{45}}default location (see (\textbf{Reference: GAP Root Directories})).
Below we describe the installation procedure for the \texttt{.tar.gz} archive format. Installation using other archive formats is performed in a
similar way.
It may be unpacked in one of the following locations: \begin{itemize} \item in the \texttt{pkg} directory of your \textsf{GAP}{\nobreakspace}4 installation; \item or in a directory named \texttt{.gap/pkg} in your home directory (to be added to the \textsf{GAP} root directory unless \textsf{GAP} is started with \texttt{\texttt{\symbol{45}}r} option); \item or in a directory named \texttt{pkg} in another directory of your choice (e.g.{\nobreakspace}in the directory \texttt{mygap} in your home directory). \end{itemize}
In the latter case one one must start \textsf{GAP} with the \texttt{\texttt{\symbol{45}}l} option, e.g.{\nobreakspace}if your private \texttt{pkg} directory is a subdirectory of \texttt{mygap} in your home directory you might type:
where \mbox{\texttt{\mdseries\slshape myhomedir}} is the path to your home directory, which (since \textsf{GAP}{\nobreakspace}4.3) may be replaced by a tilde (the empty path before the
semicolon is filled in by the default path of the \textsf{GAP}{\nobreakspace}4 home directory). }
\section{\textcolor{Chapter }{Compiling Binaries of the Ferret Package}}\label{Compiling Binaries of the Ferret Package} \logpage{[ 3, 2, 0 ]} \hyperdef{L}{X7DB615628530240D}{}
{
After unpacking the archive, go to the newly created \texttt{ferret} directory and call \texttt{./configure} to use the default \texttt{../..} path to the \textsf{GAP} home directory or \texttt{./configure \mbox{\texttt{\mdseries\slshape path}}} where \mbox{\texttt{\mdseries\slshape path}} is the path to the \textsf{GAP} home directory, if the package is being installed in a
non\texttt{\symbol{45}}default location. So for example if you install the
package in the \texttt{\texttt{\symbol{126}}/.gap/pkg} directory and the \textsf{GAP} home directory is \texttt{\texttt{\symbol{126}}/gap4r5} then you have to call
This will fetch the architecture type for which \textsf{GAP} has been compiled last and create a \texttt{Makefile}. Now simply call
\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
make \end{Verbatim}
to compile the binary and to install it in the appropriate place. }
\section{\textcolor{Chapter }{Loading the Ferret Package}}\label{Loading the Ferret Package} \logpage{[ 3, 3, 0 ]} \hyperdef{L}{X7BA03640834E607E}{}
{
To use the Ferret Package you have to request it explicitly. This is done by
calling \texttt{LoadPackage} (\textbf{Reference: LoadPackage}):
If you want to load the Ferret package by default, you can put the \texttt{LoadPackage} command into your \texttt{gaprc} file (see Section{\nobreakspace} (\textbf{Reference: The gap.ini and gaprc files})). }
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
