Schreier-Sims algoritmus

Schreier-Sims algoritmus
Earl Cayley Group $S_4$
Pojmenoval podle	Charles Sims a Otto Schreyer
Autor	Charles Sims
účel	Určení řádu permutační grupy
Datová struktura	Permutace
nejhorší čas	$O(n^{3}m+n^{6})$

Algoritmus Schreier-Sims je algoritmus z oblasti výpočetní teorie grup , který umožňuje po jediném provedení v lineárním čase najít pořadí skupiny generované permutacemi , zkontrolovat, zda prvek do takové skupiny patří a vyjmenovat její prvky. . Algoritmus navrhl Charles Sims v roce 1970 k nalezení primitivních permutačních grup [1] a je založen na Schreierově lemmatu generování podskupin [2] . Reprezentace permutační grupy, kterou algoritmus najde, je podobná stupňovité formě matice pro její řádkový prostor [3] . Metody vyvinuté Simsem tvoří základ nejmodernějších algoritmů pro práci s permutačními skupinami [4] , modifikace algoritmu se používají i v moderních systémech počítačové algebry jako GAP a Magma [5] . Jednou z nejzřejmějších aplikací algoritmu je, že jej lze použít k řešení Rubikovy kostky [6] .

Historie

Jedním z hlavních problémů teorie permutačních grup je hledání permutačních grup daného stupně (tedy minimálního počtu prvků množiny, jejíž permutační grupa obsahuje danou permutační grupu). Do roku 1970 byly pro mocniny 2 až 11 nalezeny všechny permutační grupy, pro mocniny 12 až 15 všechny tranzitivní grupy (tj. podgrupy působící tranzitivně na generátoru ) a pro mocniny 16 až 20 pouze primitivní skupiny byly nalezeny permutace . Pro hledání primitivních skupin vyššího stupně vyvinul Charles Sims program, který najde řád a nějakou strukturu v permutační skupině dané její generující množinou [1] .

Původní program zmíněný v Simsově článku byl napsán pro IBM 7040 na Rutgers University a podporoval jakoukoli skupinu, jejíž míra byla nižší než 50 [7] . Přesný odhad doby běhu algoritmu poprvé provedli Furst, Hopcroft a Lax v roce 1980 [8] . Průběžnou dobu zlepšil Jerrum v roce 1982 [9] a Donald Knuth v roce 1981 [10] . V roce 1980 byla vyvinuta efektivní pravděpodobnostní verze algoritmu [11] . Různé varianty algoritmu, včetně těch, které používají Schreierův vektor místo orbitového stromu, byly rozebrány Sheresh v roce 2003 [12] [13] .

Ve výpočetní teorii grup jsou algoritmy nad permutačními grupami jednou z nejrozvinutějších oblastí a dokonce i dnes je většina těchto algoritmů založena na metodách vyvinutých Simsem [4] .

Hlavní myšlenka

Efektivita výpočtů s permutační skupinou v podstatě závisí na tom, jak je specifikována v programu [2] . Jedním z účinných způsobů, jak toho dosáhnout, je izolovat řadu jejích podskupin a vybrat jedinečné množiny pro každou podskupinu v této řadě vzhledem k jejímu předchůdci. Algoritmus navržený Charlesem Simsem najde řadu podskupin, ve kterých každá další skupina je stabilizátorem té předchozí. Posloupnost bodů, pro které jsou stabilizátory konstruovány, se nazývá základ a množina obsahující generující prvky pro každou skupinu v řadě se nazývá silná generující množina [2] .

Algoritmus zkonstruuje základ a silnou generátorovou množinu pro permutační podskupinu danou její generátorovou sadou , pomocí Schreierova lemmatu k nalezení množin generátorů. Velikost množin získaných v mezikrokech roste exponenciálně, proto byly vyvinuty varianty algoritmu, které snižují počet uvažovaných generujících prvků [2] .

Výše popsaná reprezentace rozděluje skupinu na součin podmnožin v ní vnořených, podobně jako kroková reprezentace rozděluje vektorový prostor na přímý součet podprostorů v něm vnořených [3] .

Prohlášení o problému

Symetrická grupa je grupa, jejíž prvky jsou permutacemi prvků nějaké množiny . Obvykle se jako taková sada bere . V takovém zápisu lze na prvky grupy nahlížet jako na zobrazení , která do sebe berou množinu , tedy její automorfismy . Skupinovou operací v takovém zápisu je složení permutací, pro permutace a definované jako , kde pro . V souladu s tím bude jednotková permutace taková permutace, že , a obrácená permutace může být dána jako [14] . $S_{n}$ $\Omega$ ${\displaystyle \Omega =\{1,2,\tečky ,n\))$ $\sigma :\Omega \to \Omega$ $\Omega$ $\sigma_1$ $\sigma_2$ ${\displaystyle \sigma =\sigma _{1}\sigma _{2))$ $\sigma (\omega )=\sigma _{1}(\sigma _{2}(\omega ))$ $\omega \in \Omega$ $\sigma$ $\sigma (\omega )=\omega$ $\sigma ^{-1}(\sigma (\omega ))=\omega$

Dovolit je množina permutací délky . Vygenerovaná podskupina množiny je nejmenší inkluzní podskupinou , která obsahuje jako podmnožinu nebo ekvivalentně podskupinu všech prvků , které lze reprezentovat jako konečný součin prvků a jejich inverzí. Pořadí permutační grupy je počet prvků v ní a její stupeň je mohutnost množiny , na kterou působí. V takovém zápisu by měl být algoritmus schopen [7] : ${\displaystyle S=\{g_{1},\tečky ,g_{m}\}\subset S_{n))$ $n$ $S$ $\langle S\rangle$ $S$ $S_{n}$ $S$ $S$ $|S|$ $|\Omega |$

Získejte pořadí podskupiny generované danými permutacemi , ${\textstyle |\langle S\rangle |}$
Permutací zkontrolujte , zda leží ve vygenerované podskupině , $G$ $\langle S\rangle$
Sekvenční seznam prvků generované podskupiny bez opakování.

Aplikace

Modifikace algoritmů jsou implementovány ve dvou nejpopulárnějších systémech počítačové algebry specializovaných na výpočetní teorii grup — GAP a Magma [5] . Nástroje pro práci s permutačními skupinami, včetně algoritmů pro výčet cosetů a algoritmu Schreier-Sims, jsou také dostupné v obecnějších populárních systémech Maple a Mathematica [15] . Zpočátku byl algoritmus vyvinut pro hledání primitivních permutačních grup daného stupně [1] , ale následně se rozsah jeho použití mnohonásobně rozrostl - například pomocí tohoto algoritmu lze nalézt řešení pro danou konfiguraci Rubikovy kostky , jelikož její rotace tvoří skupinu [6] . Algoritmus se také dobře ukázal při práci s maticovými skupinami [16] .

Algoritmus

Faktorizace skupiny

Dovolit být podgrupou nějaké konečné grupy , označované transverzálem rodiny levých coset . Jakýkoli prvek může být jednoznačně reprezentován jako , where a . Postupnou aplikací tohoto výsledku na a jeho podskupiny jej lze zobecnit v následující podobě [3] [17] : $H$ $G$ $G/H$ $\{gH:g\in G\}$ $g\in G$ $g=th$ $t\in G/H$ $h\v H$ $H$

Dovolit být řada podskupin . Potom může být jakýkoli prvek jednoznačně reprezentován jako , where . ${\displaystyle G=G^{(0)}\geq G^{(1)}\geq \dots \geq G^{(k)}=\{e\))$ $G$ $g\in G$ ${\displaystyle g=g_{1}g_{2}\tečky g_{k))$ $g_{1}\in G^{(0)}/G^{(1)},g_{2}\in G^{(1)}/G^{(2)},\dots, g_{k}\in G^{(k-1)}/G^{(k)}$

Výpočet pořadí a výpis prvků

Výše popsaný pohled má následující vlastnosti:

Podle Lagrangeova teorému lze řád grupy vypočítat pomocí vzorce [3] , ${\textstyle |G|=|G^{(0)}/G^{(1)}|\times |G^{(1)}/G^{(2)}|\times \dots \times | G^{(k-1)}/G^{(k)}|}$
Prvky skupiny lze vyčíslit výčtem všech možných reprezentací [7] . ${\displaystyle g=g_{1}g_{2}\tečky g_{k))$

Abychom mohli také zkontrolovat, zda prvky patří do vygenerované podskupiny, je nutné uvažovat řadu podgrup speciálního tvaru, konkrétně podskupiny složené ze stabilizátorů [7] .

Orbity a stabilizátory

Nechte působit na sadě . Vybereme si množinu prvků a sestrojíme řadu podskupin tak, že kde je stabilizátor prvku . Jinými slovy, je podskupinou prvků , které převádějí každý z prvků do sebe [7] . S tímto přístupem se v každém dalším kroku část množiny , na kterou netriviálně působí další podskupina , sníží o jeden prvek a pořadí podskupiny, se kterou se pracuje, bude nejméně dvojnásobné. . Z toho vyplývá, že před nalezením požadovaného oddílu bude nutné provést iterace algoritmu [18] . $G$ $\Omega$ ${\textstyle \omega _{1},\tečky ,\omega _{k}\in \Omega }$ ${\textstyle G^{(i)}=G_{\omega _{i}}^{(i-1)))$ ${\displaystyle G_{\omega }=\{g:g\omega =\omega \))$ $\omega$ ${\textstyle G^{(i)))$ $G$ ${\textstyle \omega _{1},\tečky ,\omega _{i))$ $\Omega$ $G$ $\min(|\Omega |,\log |G|)$

Ke konstrukci kosset je potřeba využít faktu, že mezi prvky orbity a levými kosetami stabilizátoru existuje korespondence jedna ku jedné (bijekce) [19] . $G\omega$ ${\textstyle G/G_{\omega ))$ ${\textstyle G_{\omega ))$

Důkaz

Podle věty o drahách a stabilizátorech jsou množina koset a oběžná dráha výkonově ekvivalentní. Přiřaďte každý prvek prvku oběžné dráhy . ${\displaystyle G/G_{\omega ))$ $G\omega$ ${\displaystyle t\in G/G_{\omega ))$ $t\omega$

Nechte , pak se množiny a shodují. Ale z toho vyplývá, že se také shodují a : $t_{1}G_{\omega }=t_{2}G_{\omega }$ $(t_{1}G_{\omega })\omega$ $(t_{2}G_{\omega })\omega$ $t_{1}\omega$ $t_{2}\omega$

t jeden ω = t jeden ( G ω ω ) = ( t jeden G ω ) ω = ( t 2 G ω ) ω = t 2 ( G ω ω ) = t 2 ω {\displaystyle t_{1}\omega =t_{1}(G_{\omega }\omega )=(t_{1}G_{\omega })\omega =(t_{2}G_{\omega })\ omega =t_{2}(G_{\omega }\omega )=t_{2}\omega }

t_{1}\omega =t_{1}(G_{\omega }\omega )=(t_{1}G_{\omega })\omega =(t_{2}G_{\omega })\ omega =t_{2}(G_{\omega }\omega )=t_{2}\omega

Každé kosetě byl přiřazen přesně jeden prvek oběžné dráhy. Protože cosety pokrývají celou skupinu , jsou všechny spárované prvky odlišné. Jde tedy skutečně o bijekci. ■ $G$

Z důkazu vyplývá, že jako zástupce kosset lze brát prvky realizující různé body oběžné dráhy [19] . $G\omega$

Kontrola vlastnictví

Označte takovým prvkem , že . Rozdělení na řadu stabilizátorů vám umožní zkontrolovat, zda prvek patří do skupiny [7] : $\overline u$ ${\displaystyle G/G_{\omega ))$ ${\overline {u}}\omega =u$

Jestliže , pak existuje prvek takový , že , tj . ${\displaystyle g\in G^{(i-1)))$ ${\displaystyle t_{i}\in G^{(i-1)}/G^{(i)))$ ${\displaystyle g\in t_{i}G^{(i)))$ ${\displaystyle t_{i}^{-1}g\in G^{(i)))$
Na základě bijekce mezi prvky sousední třídy a body oběžné dráhy lze jednoznačně určit, že . $t_{i}={\overline {g(\omega _{i})}}$

Tyto vlastnosti umožňují provést přechod z do , což nakonec povede k tomu, že aktuální prvek by měl ležet v . Pokud tomu tak skutečně je, pak , odkud je možné vyjádřit [7] . ${\displaystyle G^{(i-1)))$ $G^{(i)}$ $G^{(k)}=\{e\}$ $e=t_{k}^{-1}\dots t_{2}^{-1}t_{1}^{-1}g$ ${\displaystyle g=t_{1}t_{2}\tečky t_{k))$

Výpočet oběžné dráhy

Nechte skupinu mít generovací sadu . Dráhu libovolného prvku pod působením skupiny lze organizovat do stromu následujícího tvaru [17] : $G$ $S$ $\alpha$ $G=\langle S\rangle$

Prvek je zapsán v kořeni stromu , $\alpha \in \Omega$
V každém vrcholu stromu je zapsán nějaký prvek z oběžné dráhy prvku , ${\textstyle \beta \in G(\alpha )}$ $\alpha$
Na hraně vedoucí od vrcholu s prvkem k vrcholu s prvkem je prvek takový, že . $u$ $proti$ $v S$ $s(u)=v$

Popsaný strom lze sestavit hloubkovým procházením, k tomu je nutné třídit prvek v každém vrcholu , dokud se neukáže, že vrchol ještě nebyl přidělen [17] . Příklad implementace v Pythonu : $u$ $v S$ $s(u)$

# Sestaví orbitový strom daný element w a vygeneruje sadu S def build_schreier_tree ( w , S , orbit ): pro g v S : pokud g [ w ] není na oběžné dráze : orbit [ g [ w ]] = použít ( g , orbit [ w ]) build_schreier_tree ( g [ w ], S , orbita )

Zde funkce vrátí výsledek použití operace skupiny na prvky a jako první a druhý argument a prvek je uložen v . ${\mathsf {použít}}(a,b)$ $A$ $b$ ${\mathsf {orbit}}[\alpha ]$ $\overline {\alpha }$

Schreierovo lemma

Ze Schreierova lemmatu vyplývá, že stabilizátor je generován množinou Schreierových generátorů: . Tento výsledek nám umožňuje sestavit generující množinu pro z generující množiny pro a oběžné dráhy prvku . Možná implementace pro funkci, která vrací novou generující sadu [20] : ${\displaystyle G_{\alpha ))$ $G_{\omega }=\langle \{({\overline {su)))^{-1}s{\overline {u}}\mid u\in G\omega ,s\in S\} \rangle$ ${\displaystyle G^{(w-1)))$ $\omega$ ${\displaystyle G^{(\omega )))$

# Vezme sadu generátorů pro G_{w-1} a orbit w # Vrátí sadu generátorů pro G_w def make_gen ( S , orbit ): n = len ( next ( iter ( S ))) newS = set () for s v S : pro u na oběžné dráze : newS . přidat ( snížit ( aplikovat , [ inverzní ( oběžná dráha [ s [ u ]]), s , oběžná dráha [ u ]])) vrátit novéS

Algoritmus tím není vyčerpán, protože ačkoli velikost nové generující množiny závisí polynomiálně na velikosti orbity a staré generující množiny pro jedno jednotlivé volání, v souhrnu pro všechna volání této funkce je velikost generující množiny množina roste exponenciálně [2] .

Prosévací generátory

Aby se zabránilo nekontrolovanému růstu generátorových soustrojí, musí být aplikován postup prosévání . To by vyžadovalo následující prohlášení [3] [20] :

Nechte _ Pak je možné sestrojit množinu maximálně prvků tak, že . $S\podmnožina G$ $S'$ $\vert \Omega \vert ^{2}$ $\langle S'\rangle =\langle S\rangle$

Důkaz

Nejprve dokažme následující lemma:

Nechte _ Potom se následující transformace nezmění : $S\podmnožina G$ $\langle S\rangle$

Náhrada za $v S$ $s^{{-1}}$
Nahrazení za , kde a $v S$ $st$ $t\in S$ $t\neq s$

Důkaz

Nechť po aplikaci jedné z těchto operací dostaneme množinu . Je zřejmé, že . Na druhou stranu lze tyto konverze zvrátit konverzemi stejného typu, takže . Takže . ■ $S'$ $S'\subset \langle S\rangle$ $S\subset \langle S'\rangle$ $\langle S\rangle =\langle S'\rangle$

Pomocí takových transformací můžeme množinu zredukovat do takové podoby, že pro každou dvojici v množině existuje maximálně jeden prvek takový, že: $S$ $(i,j)$ $s$

s ( ω jeden ) = ω jeden , s ( ω 2 ) = ω 2 , … , s ( ω i − jeden ) = ω i − jeden , s ( ω i ) = ω j ≠ ω i {\displaystyle s(\omega _{1})=\omega _{1},\ s(\omega _{2})=\omega _{2},\tečky ,\ s(\omega _{i- 1})=\omega _{i-1},\ s(\omega _{i})=\omega _{j}\neq \omega _{i}}

s(\omega _{1})=\omega _{1},\ s(\omega _{2})=\omega _{2},\tečky ,\ s(\omega _{i- 1})=\omega _{i-1},\ s(\omega _{i})=\omega _{j}\neq \omega _{i}

Toho lze dosáhnout přidáváním prvků do nové množiny jeden po druhém a postupem podobně jako Gaussova metoda :

S'

Řekněme, že chceme přidat nový prvek , $S'$ $s$
Pojďme postupně ${\displaystyle \omega _{1},\tečky ,\omega _{n))$
1. Pokud , tak přejděte na , ${\displaystyle s(\omega _{i})=\omega _{i))$ $\omega _{i+1}$
2. Pokud , pak zkontrolujte , zda prvek s takovým párem již nebyl nalezen , ${\displaystyle s(\omega _{i})=\omega _{j))$ $t$ $(i,j)$
  1. Pokud jsme se setkali, nahraďte je a přejděte na , $s$ $s^{-1}t$ $\omega _{i+1}$
  2. V opačném případě si zapamatujte, co odpovídá dvojici , a přidejte v aktuálním tvaru do , $s$ $(i,j)$ $s$ $S'$
Pokud do konce algoritmu máme , pak to ignorujeme a neměníme . $s=e$ $s$ $S'$

Tento algoritmus používá pouze základní operace uvedené výše, proto . Všimněte si, že if , then , takže přechod do z v algoritmu je správný a každý pár ve skutečnosti odpovídá ne více než jedné permutaci. Vezmeme-li v úvahu, že takových dvojic je nejvíce , získáme požadované tvrzení.

■

\langle S'\rangle =\langle S\rangle

s(\omega _{i})=t(\omega _{i})

{\displaystyle s^{-1}t(\omega _{i})=\omega _{i))

\omega _{i+1}

s^{-1}t

(i,j)

n^{2}

Postup popsaný v důkazu se nazývá Sims filtr a funguje v [21] . Jeho implementace může vypadat takto: $O(|S|\cdot \Omega ^{2})$

# Vezme nadřazenou množinu S # Vrátí ztenčenou nadřazenou množinu S' def normalize ( S ): n = len ( další ( iter ( S ))) newS = sada () základ = [{} pro i v rozsahu ( n )] for s v S : pro x v rozsahu ( 0 , n ): if s [ x ] != x : if s [ x ] v základu [ x ]: s = platí ( inverzní ( s ), základ [ x ][ s [ x ]]) else : základ [ x ][ s [ x ]] = s newS . přidat ( s ) přerušit návrat novinkyS

Kromě filtru Sims lze pro vyhledání malé sady použít filtr Jerrum [22] . Na rozdíl od filtru Sims, který najde množinu maximálně prvků, filtr Jerrum najde množinu maximálně prvků. Zároveň funguje filtr Jerrum pro , takže v případě algoritmu Schreier-Sims je vhodnější použít filtr Sims [21] . $S'$ $|\Omega |^{2}$ $|\Omega |$ $O(|S|\cdot |\Omega |^{4})$

Algoritmus

Vše výše uvedené dohromady dává algoritmus, který lze stručně implementovat následovně [20] :

# Vezme generující množinu S = s1, ..., sk # Vrátí transverzály koset U1, ..., Uk def schreier_sims ( S ): n = len ( další ( iter ( S ))) ans = [] w = 0 zatímco S : orbita = {} orbita [ w ] = n-tice ( rozsah ( n )) build_schreier_tree ( w , S , orbit ) ans += [[ orbit [ i ] pro i na oběžné dráze ]] S = normalizovat ( make_gen ( S , orbit )) w += 1 návrat ans

Krok za krokem mají jeho akce následující význam:

Oběžná dráha prvku je postavena hledáním do hloubky, $\omega _{i}$
Všechny generátory Schreier jsou vypočteny pro , ${\displaystyle G^{(i+1)))$
Mnoho generátorů je zdecimováno, aby se zabránilo jejich exponenciálnímu růstu.

Na výstupu algoritmus vrátí seznam, jehož prvky jsou transverzály coset . $G^{(0)}/G^{(1)},G^{(1)}/G^{(2)},\dots ,G^{(k-1)}/G^ {(k)}$

Doba běhu algoritmu

Celkově algoritmus nevyžaduje žádné další iterace. Každá iterace se skládá z: $|\Omega |$

Vybudování orbitálního stromu, který vyžaduje základní operace, $O(|S|\cdot |\Omega |)$
Konstrukce Schreierových generátorů, která přebírá základní operace a vrací generátory, $O(|S|\cdot |\Omega |^{2})$ $|S|\cdot |\Omega |$
Normalizace generující množiny, která provádí elementární operace, kde je množina získaná v předchozím kroku. $O(|S'|\cdot |\Omega |^{2})$ $S'$

Hodnota v případě, že je zadána množina, se v průběhu algoritmu nemění a je rovna . Velikost generující sady je zpočátku rovna a v každém následujícím kroku nepřesahuje . Celkovou dobu běhu algoritmu ve výše uvedené implementaci lze tedy odhadnout jako [8] [12] [13] . $|\Omega |$ ${\displaystyle S=\{g_{1},\tečky ,g_{m}\}\subset S_{n))$ $n$ $m$ $|\Omega |^{2}=n^{2}$ $O(n^{3}m+n^{6})$

Variace algoritmu

Pseudolineární verze

Dříve se ukázalo, že algoritmus vyžaduje iterace. V obecném případě může být velikost skupiny řádově , a v tomto případě podle Stirlingova vzorce , který je samozřejmě větší . Ale v některých případech je řád skupiny malý, a proto je výhodnější mít algoritmus, který závisí na , a nikoli - například pokud jde o nějakou známou skupinu, která je dána jako permutační skupina [12] . $\min(|\Omega |,\log |G|)$ $n!$ $\log |G|\sim n\log n$ $|\Omega |=n$ $\log |G|$ $n$

Podle Cayleyho teorému je jakákoli konečná grupa izomorfní k nějaké permutační grupě . Stupeň takové skupiny může být velký, ale u mnoha skupin je jejich pořadí takové, že . Například dihedrální skupina je izomorfní k permutační skupině generované cyklickým posunem a odrazem . To znamená, že stupeň této skupiny je , a pořadí je , a . Pro takové skupiny lze uvažovat o algoritmech s dobou běhu , které se nazývají pseudolineární [12] . $n$ $|G|$ $\log |G|<n$ $D_{n}$ $r=(1~~2~~\dots~~n)$ $s=(1~~n)(2~~n-1)(3~~n-2)\tečky$ $n$ $2n$ $\log |G|\sim \log n$ $O(nm\log ^{c}|G|)$

Ve snaze přiblížit algoritmus pseudo-lineárnímu a snížit stupeň , zahrnutý v jeho době běhu, Sheresh dospěl k verzím algoritmu, které vyžadují [18] : $n$

$O(n^{2}\log ^{3}|G|+mn^{2}\log |G|)$ čas a paměť $O(n^{2}\log |G|+mn)$
$O(n^{3}\log ^{3}|G|+mn^{3}\log |G|)$ čas a paměť. $O(n\log ^{2}|G|+mn)$

Pravděpodobnostní verze

První pracovní pravděpodobnostní verze algoritmu byla vyvinuta Jeffrey Leonem v roce 1980 [11] . Obvykle to mají na mysli, když mluví o pravděpodobnostní Schreyer-Simsově metodě. V něm byl tento postup při ztenčování Schreierových generátorů předčasně ukončen, pokud se ukázalo, že 20 generátorů v řadě bylo faktorizováno. Sheresh ukázal, že spolu s některými optimalizacemi dává tento postup následující tvrzení [5] :

Pro jakoukoli konstantu existuje algoritmus typu Monte Carlo , který s pravděpodobností chyby nanejvýš zkonstruuje silnou sadu generátorů pro permutační skupinu pomocí času a paměti. $d$ ${\displaystyle n^{-d))$ $G=\langle S\rangle$ $O(n\log n\log ^{4}|G|+mn\log |G|)$ $O(n\log |G|+mn)$

V moderních systémech počítačové algebry se obvykle pro zrychlení programu používají modifikace této verze algoritmu s různou heuristikou [5] .

Poznámky

↑ 1 2 3 Sims, 1970 , str. 169-170.
↑ 1 2 3 4 5 Murray, 2003 , str. 1-3.
↑ 1 2 3 4 5 Holt, Eyck, O'Brien, 2005 , str. 87-90.
↑ 1 2 Sheresh, 2003 , str. 1-4.
↑ 1 2 3 4 Sheresh, 2003 , str. 62-64.
↑ 1 2 Brouwer, 2016 , str. čtyři.
↑ 1 2 3 4 5 6 7 Sims, 1970 , str. 176-177.
↑ 1 2 Furst, Hopcroft, Lax, 1980 .
↑ Jerrum, 1986 .
↑ Knuth, 1991 .
↑ 1 2 Leon, 1980 .
↑ 1 2 3 4 Sheresh, 2003 , str. 48-54.
↑ 1 2 Holt, Eyck, O'Brien, 2005 , str. 93-94.
↑ Zhuravlev, Flerov, Vjaly, 2019 , Permutace, str. 31-36.
↑ Holt, Eyck, O'Brien, 2005 , str. 1-7.
↑ Murray, O'Brien, 1995 .
↑ 1 2 3 Murray, 2003 , str. 9-24.
↑ 1 2 Sheresh, 2003 , str. 59-62.
↑ 1 2 Zhuravlev, Flerov, Vjaly, 2019 , Orbity a stabilizátory, str. 140-145.
↑ 1 2 3 Murray, 2003 , str. 25-33.
↑ 1 2 Vipul Naik. Sims filter (anglicky) . Groupprops, Wiki vlastnosti skupiny . Staženo 23. září 2019. Archivováno z originálu 1. září 2019.
↑ Vipul Naik. Jerrumův filtr . Groupprops, Wiki vlastnosti skupiny . Získáno 19. září 2023. Archivováno z originálu 1. září 2019.

Literatura

Yu. I. Zhuravlev , Yu. A. Flerov a M. N. Vjaly Základy vyšší algebry a teorie kódování . - FUPM MIPT, 2019. - S. 144. - 305 s.
Charles C. Sims. Výpočetní metody ve studiu permutačních grup (anglicky) // Computational Problems in Abstract Algebra. - Elsevier, 1970. - S. 176-177. — ISBN 9780080129754 .
Derek F. Holt, Bettina Eick, Eamonn A. O'Brien. Handbook of Computational Group Theory (anglicky) . — New York: Chapman and Hall/CRC, 2005. — 536 s. — ISBN 9780429147944 .
Merrick Furst, John Hopcroft, Eugene Luks. Polynomiální-časové algoritmy pro permutační skupiny (anglicky) // 21. výroční symposium o základech počítačových věd (sfcs 1980). - IEEE, 1980. - doi : 10.1109/sfcs.1980.34 .
Scott H. Murray. Algoritmus Schreier-Sims (anglicky) // Katedra matematiky, Australian National University. — 2003.
TC Brouwer. Řešení hádanky libovolné permutace (anglicky) // Mathematisch Instituut, Universiteit Leiden. — 2016.
Ákos Seress. Permutation Group Algorithms (anglicky) // Cambridge Core. - 2003. - ISBN 9780511546549 . - doi : 10.1017/CBO9780511546549 .
Mark Jerrum. Kompaktní znázornění permutačních skupin (anglicky) // Journal of Algorithms. - 1986. - Sv. 7 , iss. 1 . — S. 60–78. — ISSN 0196-6774 . - doi : 10.1016/0196-6774(86)90038-6 .
Donald E. Knuth. Efektivní zastoupení skupin perm (anglicky) // Combinatorica. - 1991. - Sv. 11 , iss. 1 . — S. 33–43. — ISSN 1439-6912 0209-9683, 1439-6912 . - doi : 10.1007/bf01375471 .
Jeffrey S. Leon O algoritmu pro nalezení báze a silné generující množiny pro skupinu dané generováním permutací // Matematika výpočtu. - 1980. - Sv. 35 , iss. 151 . - S. 941-974. — ISSN 0025-5718 . - doi : 10.1090/s0025-5718-1980-0572868-5 .
Scott H. Murray, EA O'Brien. Výběr základních bodů pro Schreier-Simsův algoritmus pro maticové skupiny // Journal of Symbolic Computation. - 1995. - Sv. 19 , iss. 6 . - S. 577-584. — ISSN 0747-7171 . - doi : 10.1006/jsco.1995.1033 .

Teorie skupin
Základní pojmy	Podskupina Normální podskupina Faktorová skupina Práce Přímo polopřímý volný, uvolnit
Algebraické vlastnosti	komutativní skupina Cyklická skupina objednaná skupina Transformovat skupinu Řešitelná skupina Schreierovo lemma Lagrangeova věta Sylowovy věty Klasifikace jednoduchých konečných grup
konečné skupiny	Konečná cyklická grupa C n Symetrická grupa S n Dihedrální skupina D n Střídavá skupina A n Klein čtyřčlenná skupina Mathieu skupiny M11 _ M12 _ M22 _ M23 _ M24 _ Conwayovy skupiny Co 1 Co2 _ Co3 _ Janko skupiny J1 _ J2 _ J3 _ J4 _ Rybářské skupiny F22 _ F 23 F24 _ monstrum (M)
Topologické skupiny	Skupiny lži Ortogonální skupina O(n) Speciální ortogonální grupa SO(n) Unitární skupina U(n) Speciální unitární skupina SU(n) Symplectic group Sp(n) Výjimečně jednoduché Lorentzova skupina Skupina Poincaré
Algoritmy na skupinách	Schreier - Sims Todd - Coxeter Fourierova transformace