<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (orb) - Contents</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
</head>
<body>
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">Top of Book</a> <a href="chap1.html">Next Chapter</a> </div>
<p><a id="X7D2C85EC87DD46E5" name="X7D2C85EC87DD46E5"></a></p>
<div class="pcenter">
<h1>GAP 4 Package <strong class="pkg">orb</strong></h1>
<h2>orb --- Methods to enumerate Orbits</h2>
<p>
Version 2.0</p>
<p>June 2008</p>
</div>
<p><b>Jürgen Müller
</b>
<br />Email: <span class="URL"><a href="mailto:juergen.mueller@math.rwth-aachen.de">juergen.mueller@math.rwth-aachen.de</a></span>
<br />Homepage: <span class="URL"><a href="http://www.math.rwth-aachen.de/~Juergen.Mueller">http://www.math.rwth-aachen.de/~Juergen.Mueller</a></span>
<br />Address: <br />Lehrstuhl D für Mathematik, RWTH Aachen, Templergraben 64, 52062 Aachen, Germany
</p><p><b>Max Neunhöffer
</b>
<br />Email: <span class="URL"><a href="mailto:neunhoef@mcs.st-and.ac.uk">neunhoef@mcs.st-and.ac.uk</a></span>
<br />Homepage: <span class="URL"><a href="http://www-groups.mcs.st-and.ac.uk/~neunhoef">http://www-groups.mcs.st-and.ac.uk/~neunhoef</a></span>
<br />Address: <br />School of Mathematics and Statistics Mathematical Institute University of St Andrews North Haugh St Andrews, Fife KY16 9SS Scotland, UK
</p><p><b>Felix Noeske
</b>
<br />Email: <span class="URL"><a href="mailto:felix.noeske@math.rwth-aachen.de">felix.noeske@math.rwth-aachen.de</a></span>
<br />Homepage: <span class="URL"><a href="http://www.math.rwth-aachen.de/~Felix.Noeske">http://www.math.rwth-aachen.de/~Felix.Noeske</a></span>
<br />Address: <br />Lehrstuhl D für Mathematik, RWTH Aachen, Templergraben 64, 52062 Aachen, Germany
</p>
<p><a id="X81488B807F2A1CF1" name="X81488B807F2A1CF1"></a></p>
<h3>Copyright</h3>
<p>© 2005-2008 by Jürgen Müller, Max Neunhöffer and Felix Noeske</p>
<p>This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see <span class="URL"><a href="http://www.gnu.org/licenses/">http://www.gnu.org/licenses/</a></span>.</p>
<p><a id="X8537FEB07AF2BEC8" name="X8537FEB07AF2BEC8"></a></p>
<div class="contents">
<h3>Contents</h3>
<div class="ContChap"><a href="chap1.html#X7DFB63A97E67C0A1">1 <span class="Heading">Introduction</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap1.html#X7AC0DE4D8555D291">1.1 <span class="Heading">Motivation for this package</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap1.html#X786BACDB82918A65">1.2 <span class="Heading">Overview over this manual</span></a>
</div>
</div>
<div class="ContChap"><a href="chap2.html#X80F00D467DD002D3">2 <span class="Heading">Installation of the <strong class="pkg">orb</strong>-Package</span></a>
</div>
<div class="ContChap"><a href="chap3.html#X7D55DB437F5407E8">3 <span class="Heading">Basic orbit enumeration</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap3.html#X87DF498E7F386786">3.1 <span class="Heading">Enumerating orbits</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X86A89A0881CE04F6">3.1-1 Orb</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7BCD5342793C7A7E">3.1-2 Enumerate</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X81D5A4A97AA9D4B0">3.1-3 IsClosed</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X81BF5A087B9E1353">3.1-4 <span class="Heading">Options for orbits</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7B11180F80A77D48">3.1-5 <span class="Heading">Output components of orbits</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X833670F47BD5632C">3.1-6 StabWords</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X84F62CB679D6B3CE">3.1-7 PositionOfFound</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X79A6D04C7CBABFC7">3.1-8 DepthOfSchreierTree</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X81C12D677CE815C7">3.1-9 ActionOnOrbit</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7EA4E92180F142D3">3.1-10 OrbActionHomomorphism</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7F927E787BA898BF">3.1-11 TraceSchreierTreeForward</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X80615B4D83620AA1">3.1-12 TraceSchreierTreeBack</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7D892CE87E7EBEDB">3.1-13 ActWithWord</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X799D2F3C866B9AED">3.1-14 EvaluateWord</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7D100BE4820039C1">3.1-15 AddGeneratorsToOrbit</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X823F7A9A83EACFD0">3.1-16 MakeSchreierTreeShallow</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8566B13379E697F6">3.1-17 FindSuborbits</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X83015A9E823E1AB1">3.1-18 OrbitIntersectionMatrix</a></span>
</div>
</div>
<div class="ContChap"><a href="chap4.html#X8705763D8698C0B7">4 <span class="Heading">Hashing techniques</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap4.html#X814DE39B7C1B1554">4.1 <span class="Heading">The idea of hashing</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap4.html#X7AE36B967EB1382B">4.2 <span class="Heading">Hash functions</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7ACED4FB7C971A5A">4.2-1 ChooseHashFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X803D35D97B6E7CC5">4.2-2 ChooseHashFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7B04C17D7DC6E277">4.2-3 ChooseHashFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7F41F51C83E88759">4.2-4 ChooseHashFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X847801B87A03AA77">4.2-5 ChooseHashFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X819264A980D873EE">4.2-6 ChooseHashFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7BAD070A79E54131">4.2-7 ChooseHashFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7C7C0CDB7DCE95B4">4.2-8 ChooseHashFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X80C0C39080BFAA8F">4.2-9 ChooseHashFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X87C1B2F7871B7EA4">4.2-10 ChooseHashFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X80E195168734F8E3">4.2-11 ChooseHashFunction</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap4.html#X8424E70E78FAA203">4.3 <span class="Heading">Using hash tables</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7FD5A22A86DACF26">4.3-1 NewHT</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7D9D6CF37FA68C39">4.3-2 AddHT</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X853825AB7DE1F99C">4.3-3 ValueHT</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7D6AA1618657386C">4.3-4 InitHT</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X86E9DEC68728425C">4.3-5 GrowHT</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap4.html#X8069137484662072">4.4 <span class="Heading"> The data structures for hash tables </span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X81BD00DE877E2C0D">4.4-1 <span class="Heading"> Memory requirements </span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X8238A6C0834A48F4">4.4-2 <span class="Heading"> Handling of collisions </span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X836F7C2C7932FEAE">4.4-3 <span class="Heading"> Efficiency </span></a>
</span>
</div>
</div>
<div class="ContChap"><a href="chap5.html#X86BA72E27E278718">5 <span class="Heading">Caching techniques</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X87639FAC8621A75A">5.1 <span class="Heading">The idea of caching</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X7B269D167B6C9BF6">5.2 <span class="Heading">Using caches</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7FF40AE981FE6F75">5.2-1 LinkedListCache</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7ECBA1228365BDC4">5.2-2 CacheObject</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7E1D239886BC762C">5.2-3 ClearCache</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X819FD13C7CCC6810">5.2-4 UseCacheObject</a></span>
</div>
</div>
<div class="ContChap"><a href="chap6.html#X8151A51884B7EE2C">6 <span class="Heading">Random elements</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap6.html#X83F87C898304A0C8">6.1 <span class="Heading">Randomizing mutable objects</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X83DD8B39864A2C94">6.1-1 Randomize</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7BBA80B882867C36">6.1-2 MakeRandomVectors</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7DF0A6E885A4EE42">6.1-3 MakeRandomLines</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap6.html#X7B46C06479401BED">6.2 <span class="Heading">Product replacement</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X8290E4C57DE25CD4">6.2-1 ProductReplacer</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7AB4297E78216855">6.2-2 Next</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7EAED8EB78CCEDE2">6.2-3 Reset</a></span>
</div>
</div>
<div class="ContChap"><a href="chap7.html#X7DF379C283FE23EF">7 <span class="Heading">Searching in groups and orbits</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X85BB0EBC7F0D8329">7.1 <span class="Heading">Searching using orbit enumeration</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X7F6A0E447E369404">7.2 <span class="Heading">Random searches in groups</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7971BF5D8099E557">7.2-1 RandomSearcher</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X835FBD72853595BE">7.2-2 Search</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X833CDEF4843DF5C5">7.3 <span class="Heading">The dihedral trick and applications</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X84659F6786852150">7.3-1 FindInvolution</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7FBBCD5C82211934">7.3-2 FindCentralisingElementOfInvolution</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X80CEAEAB7EDB57FE">7.3-3 FindInvolutionCentralizer</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X7DE53BFB7A82324D">7.4 <span class="Heading">Orbit statistics on vector spaces</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X80E95A9D82ADB62D">7.4-1 OrbitStatisticOnVectorSpace</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8124E7F17C95BECB">7.4-2 OrbitStatisticOnVectorSpaceLines</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X7F051A447E2E8573">7.5 <span class="Heading">Finding generating sets of subgroups</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X80BB35D380A972BB">7.5-1 FindShortGeneratorsOfSubgroup</a></span>
</div>
</div>
<div class="ContChap"><a href="chap8.html#X7CC7EC257DD466E3">8 <span class="Heading">Orbit enumeration by suborbits</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap8.html#X819508B17A733D53">8.1 <span class="Heading"><code class="code">OrbitBySuborbits</code> and its resulting objects</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X79B161FD84AB8C68">8.1-1 OrbitBySuborbit</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X86CCD9B98156155E">8.1-2 OrbitBySuborbitKnownSize</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X83C66D4A8603CA56">8.1-3 Size</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X7EBEA64D7A5F78E3">8.1-4 Seed</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X80B78B657E77A485">8.1-5 SuborbitsDb</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X7B5E783478A337C9">8.1-6 WordsToSuborbits</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X7926C96485985614">8.1-7 Memory</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X840AFA7987535AC5">8.1-8 Stabilizer</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X7F496D9B7C44DAAB">8.1-9 StabWords</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X802068267DACF3F6">8.1-10 SavingFactor</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X79DB081F827B53CB">8.1-11 TotalLength</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X81ABF8407AF16C34">8.1-12 Representatives</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X79552A1086449062">8.1-13 SavingFactor</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X7A96D6D37F0EC46A">8.1-14 OrigSeed</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap8.html#X7C0335D97C990559">8.2 <span class="Heading">Preparation functions for <code class="func">OrbitBySuborbit</code> (<a href="chap8.html#X79B161FD84AB8C68"><b>8.1-1</b></a>)</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X830E221D84E44A64">8.2-1 OrbitBySuborbitBootstrapForVectors</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X799056597EA62513">8.2-2 OrbitBySuborbitBootstrapForLines</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X7919B1AB7D68780D">8.2-3 OrbitBySuborbitBootstrapForSpaces</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap8.html#X80F036B378A3FD32">8.3 <span class="Heading">Data structures for orbit-by-suborbits</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X7CFD48C17B48CDDD">8.3-1 IsOrbitBySuborbitSetup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X855663F5790EA2D0">8.3-2 <span class="Heading">The global record <code class="code">ORB</code></span></a>
</span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap8.html#X8696CFD08768508D">8.4 <span class="Heading">Lists of orbit-by-suborbit objects</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X7FB77D827E31AE24">8.4-1 InitOrbitBySuborbitList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X87CB441882F43F62">8.4-2 IsVectorInOrbitBySuborbitList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X7D82CE2579A50B2C">8.4-3 OrbitsFromSeedsToOrbitList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X83A306918461D700">8.4-4 VerifyDisjointness</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X7ED405017E3A56CD">8.4-5 Memory</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X7D52885787865E81">8.4-6 TotalLength</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X7C4255287D394742">8.4-7 Size</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X7BFE12DE85CCE143">8.4-8 SavingFactor</a></span>
</div>
</div>
<div class="ContChap"><a href="chap9.html#X7BDEA65183A3AE7B">9 <span class="Heading">Finding nice quotients</span></a>
</div>
<div class="ContChap"><a href="chap10.html#X7A489A5D79DA9E5C">10 <span class="Heading">Examples</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap10.html#X7CD0993B7A8F5DA5">10.1 <span class="Heading">The Mathieu group M_{11} acting in
dimension 24</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap10.html#X7C6E7A1A7CC73262">10.2 <span class="Heading">The Fischer group Fi_{23} acting in
dimension 1494
</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap10.html#X7D7BDBF87E7C45ED">10.3 <span class="Heading">The Conway group Co_1 acting in
dimension 24
</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap10.html#X781209EE7C9D3E0E">10.4 <span class="Heading">The Baby Monster B acting on its 2A involutions</span></a>
</div>
</div>
<br />
</div>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap1.html">Next Chapter</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
2524
