Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/images/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 27.7.2024 mit Größe 13 kB image not shown  

Quelle  chap2_mj.html   Sprache: HTML

 
 products/Sources/formale Sprachen/GAP/pkg/images/doc/chap2_mj.html


<?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>
<script type="text/javascript"
  src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (Images) - Chapter 2: Minimal and Canonical Images</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" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap2"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap1_mj.html">[Previous Chapter]</a>    <a href="chap3_mj.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap2.html">[MathJax off]</a></p>
<p><a id="X7B4A093B7FBA4C23" name="X7B4A093B7FBA4C23"></a></p>
<div class="ChapSects"><a href="chap2_mj.html#X7B4A093B7FBA4C23">2 <span class="Heading">Minimal and Canonical Images</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X7DA24AB4803F68DA">2.1 <span class="Heading">Function documentation</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X7E9EFA0E7A997586">2.1-1 MinimalImage</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X848A9B117C3EEF48">2.1-2 IsMinimalImageLessThan</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X780189E3873B7A42">2.1-3 CanonicalImage</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X803A8BB57A63C577">2.1-4 ImagesAdvancedConfig</a></span>
</div></div>
</div>

<h3>2 <span class="Heading">Minimal and Canonical Images</span></h3>

<p>Given a group G and action A, the minimal image of an object O is the smallest image of O under any element of G, under the action A.</p>

<p>As a more concrete example, let us consider the minimal image of the set [2,3,5,7] under a group G.</p>

<p>We can calculate all the images of our set under G, then choose the smallest one.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group((1,2,3)(4,5,6)(7,8,9),(1,4,7)(2,5,8)(3,6,9));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">List(G, g -> OnSets([2,3,5,7], g) );</span>
[ [ 2, 3, 5, 7 ], [ 1, 2, 4, 9 ], [ 1, 3, 6, 8 ], [ 2, 4, 8, 9 ],
  [ 1, 6, 7, 8 ], [ 3, 5, 7, 9 ], [ 1, 5, 6, 8 ], [ 3, 4, 5, 7 ],
  [ 2, 4, 6, 9 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Minimum(List(G, g -> OnSets([2,3,5,7], g) ) );</span>
[ 1, 2, 4, 9 ]
</pre></div>

<p>This is very inefficient, as it requires enumerating all members of G. The images package produces a function MinimalImage, which performs this same operation more efficiently.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">LoadPackage("images", false);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">MinimalImage(G, [2,3,5,7], OnSets);</span>
[ 1, 2, 4, 9 ]
</pre></div>

<p>The most common use of MinimalImage is to categorise objects into equivalence classes. This next example shows [2,3,5,7] and [1,6,7,8] are in the same orbit, while [3,5,7,8] is in a different orbit.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">MinimalImage(G, [2,3,5,7], OnSets);</span>
[ 1, 2, 4, 9 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">MinimalImage(G, [1,6,7,8], OnSets);</span>
[ 1, 2, 4, 9 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">MinimalImage(G, [3,5,7,8], OnSets);</span>
[ 1, 2, 6, 8 ]
</pre></div>

<p>In this situation, we do not really need the minimal image, just a method of telling if two sets are in the same equivalence class.</p>

<p>Motivated by this, this package provides CanonicalImage. CanonicalImage(G,O,A) returns some image of O by an element of G under the action A, guaranteeing that if two objects O1 and O2 are in the same orbit of G then CanonicalImage(G,O1,A) = CanonicalImage(G,O2,A). However, the canonical image is not "minimal" under any sensible ordering. The advantage of CanonicalImage is that it is much faster than MinimalImage, often by orders of magnitude.</p>

<p><strong class="button">WARNING:</strong> The value of MinimalImage will remain identical between versions of GAP and the Images package, unless bugs are discovered. This is NOT true for CanonicalImage.</p>

<p><a id="X7DA24AB4803F68DA" name="X7DA24AB4803F68DA"></a></p>

<h4>2.1 <span class="Heading">Function documentation</span></h4>

<p><a id="X7E9EFA0E7A997586" name="X7E9EFA0E7A997586"></a></p>

<h5>2.1-1 MinimalImage</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalImage</code>( <var class="Arg">G</var>, <var class="Arg">pnt</var>[, <var class="Arg">act</var>][, <var class="Arg">Config</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsMinimalImage</code>( <var class="Arg">G</var>, <var class="Arg">pnt</var>[, <var class="Arg">act</var>][, <var class="Arg">Config</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalImagePerm</code>( <var class="Arg">G</var>, <var class="Arg">pnt</var>[, <var class="Arg">act</var>][, <var class="Arg">Config</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">MinimalImage</code> returns the minimal image of <var class="Arg">pnt</var> under the group <var class="Arg">G</var>. <code class="func">IsMinimalImage</code> returns a boolean which is <code class="keyw">true</code> if <code class="func">MinimalImage</code> would return <var class="Arg">pnt</var> (so the value is it's own minimal image).



<p><code class="func">MinimalImagePerm</code> returns the permutation which maps <var class="Arg">pnt</var> to its minimal image.</p>

<p>The option <var class="Arg">Config</var> defines a number of advanced configuration   options, which are described in 'ImagesAdvancedConfig'.</p>

<p><a id="X848A9B117C3EEF48" name="X848A9B117C3EEF48"></a></p>

<h5>2.1-2 IsMinimalImageLessThan</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsMinimalImageLessThan</code>( <var class="Arg">G</var>, <var class="Arg">A</var>, <var class="Arg">B</var>[, <var class="Arg">act</var>][, <var class="Arg">config</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">IsMinimalImageLessThan</code> checks if the minimal image of <var class="Arg">A</var> under the group <var class="Arg">G</var> is smaller than <var class="Arg">B</var>.</p>

<p>It returns MinImage.Smaller, MinImage.Equal or MinImage.Larger, if the minimal image of <var class="Arg">A</var> is smaller, equal or larger than <var class="Arg">B</var>.</p>

<p>The option <var class="Arg">Config</var> defines a number of advanced configuration   options, which are described in 'ImagesAdvancedConfig'.</p>

<p><a id="X780189E3873B7A42" name="X780189E3873B7A42"></a></p>

<h5>2.1-3 CanonicalImage</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CanonicalImage</code>( <var class="Arg">G</var>[, <var class="Arg">pnt</var>][, <var class="Arg">act</var>][, <var class="Arg">Config</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsCanonicalImage</code>( <var class="Arg">G</var>[, <var class="Arg">pnt</var>][, <var class="Arg">act</var>][, <var class="Arg">Config</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CanonicalImagePerm</code>( <var class="Arg">G</var>[, <var class="Arg">pnt</var>][, <var class="Arg">act</var>][, <var class="Arg">Config</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">CanonicalImage</code> returns a canonical image of <var class="Arg">pnt</var> under the group <var class="Arg">G</var>. <code class="func">IsCanonicalImage</code> returns a boolean which is <code class="keyw">true</code> if <code class="func">CanonicalImage</code> would return <var class="Arg">pnt</var> (so the value is it's own minimal image).



<p><code class="func">CanonicalImagePerm</code> returns the permutation which maps <var class="Arg">pnt</var> to its minimal image.</p>

<p>By default, these functions use the fastest algorithm for calculating canonical images, which is often changed in new versions of the package. The option <var class="Arg">Config</var> defines a number of advanced configuration   options, which are described in 'ImagesAdvancedConfig'. These include the ability to choose the canonicalising algorithm used.</p>

<p><a id="X803A8BB57A63C577" name="X803A8BB57A63C577"></a></p>

<h5>2.1-4 ImagesAdvancedConfig</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ImagesAdvancedConfig</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This section describes the advanced configuration options for both <code class="func">MinimalImage</code> (<a href="chap2_mj.html#X7E9EFA0E7A997586"><span class="RefLink">2.1-1</span></a>) and <code class="func">CanonicalImage</code> (<a href="chap2_mj.html#X780189E3873B7A42"><span class="RefLink">2.1-3</span></a>). Assume we have called <code class="func">MinimalImage</code> (<a href="chap2_mj.html#X7E9EFA0E7A997586"><span class="RefLink">2.1-1</span></a>) or <code class="func">CanonicalImage</code> (<a href="chap2_mj.html#X780189E3873B7A42"><span class="RefLink">2.1-3</span></a>) with arguments <code class="code">(<var class="Arg">G</var>,<var class="Arg">O</var>,<var class="Arg">A</var>)</code>.</p>


<dl>
<dt><strong class="Mark"><code class="code">order</code></strong></dt>
<dd><p>The search ordering used while building the image. There are many configuration options available. We shall list here just the three most useful ones. A full list is in the paper "Minimal and Canonical Images" by the authors of this package.</p>


<dl>
<dt><strong class="Mark"><code class="code">CanonicalConfig_Minimum</code></strong></dt>
<dd><p>Lexicographically smallest set -- same as using MinimalImage.</p>

</dd>
<dt><strong class="Mark"><code class="code">CanonicalConfig_FixedMinOrbit</code></strong></dt>
<dd><p>Lexicographically smallest set under the ordering of the integers given by the MinOrbitPerm function.</p>

</dd>
<dt><strong class="Mark"><code class="code">CanonicalConfig_RareRatioOrbitFixPlusMin</code></strong></dt>
<dd><p>The current best algorithm (default)</p>

</dd>
</dl>
</dd>
<dt><strong class="Mark"><code class="code">stabilizer</code></strong></dt>
<dd><p>The group <code class="code">Stabilizer(<var class="Arg">G</var>,<var class="Arg">O</var>,<var class="Arg">A</var>)</code>, or a subgroup of this group; see <code class="func">Stabilizer</code> (<a href="../../../doc/ref/chap41_mj.html#X86FB962786397E02"><span class="RefLink">Reference: Stabilizer</span></a>). If this group is large, it is more efficient to pre-calculate it. Default behaviour is to calculate the group, pass <code class="code">Group(())</code> to disable this behaviour. This is not checked, and passing an incorrect group will produce incorrect answers.</p>

</dd>
<dt><strong class="Mark"><code class="code">disableStabilizerCheck</code> (default <code class="keyw">false</code>)</strong></dt>
<dd><p>By default, during search we perform cheap checks to try to find extra elements of the stabilizer. Pass true to disable this check, this will make the algorithm MUCH slower if the stabilizer argument is a subgroup.</p>

</dd>
<dt><strong class="Mark"><code class="code">getStab</code> (default <code class="keyw">false</code>)</strong></dt>
<dd><p>Return the calculated value of <code class="code">Stabilizer(<var class="Arg">G</var>,<var class="Arg">O</var>,<var class="Arg">A</var>)</code>. This may return a subgroup rather than the whole stabilizer.</p>

</dd>
</dl>

<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap1_mj.html">[Previous Chapter]</a>    <a href="chap3_mj.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<hr />
<p class="foot">generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>

100%


¤ Dauer der Verarbeitung: 0.36 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

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.