Schreier-Sims algoritm

Schreier-Sims algoritm
Earl Cayley Group $S_4$
Döpt efter	Charles Sims och Otto Schreyer
Författare	Charles Sims
ändamål	Bestämma ordningen för en permutationsgrupp
Datastruktur	Permutationer
värsta tiden	$O(n^{3}m+n^{6})$

Schreier-Sims- algoritmen är en algoritm från fältet beräkningsgruppteori som gör det möjligt att efter en enda exekvering i linjär tid hitta ordningen för en grupp som genereras av permutationer, kontrollera om ett element tillhör en sådan grupp och räkna upp dess element . Algoritmen föreslogs av Charles Sims 1970 för att hitta primitiva permutationsgrupper [1] och är baserad på Schreiers subgruppgenerationslemma [2] . Representationen av permutationsgruppen som algoritmen hittar är analog med stegformen för matrisen för desssträngmellanslag [3] . De metoder som Sims utvecklade utgör grunden för de flesta moderna algoritmer för att arbeta med permutationsgrupper [4] , modifieringar av algoritmen används även i moderna datoralgebrasystem som GAP och Magma [5] . En av de mest uppenbara tillämpningarna av algoritmen är att den kan användas för att lösa Rubiks kub [6] .

Historik

Ett av huvudproblemen i teorin om permutationsgrupper är sökningen efter permutationsgrupper av en given grad (det vill säga det minsta antalet element i en uppsättning vars permutationsgrupp innehåller en given permutationsgrupp). År 1970, för potenserna 2 till 11, hade alla permutationsgrupper hittats, för potenserna 12 till 15 hade alla transitiva grupper (det vill säga subgrupper som agerar transitivt på en genereringsmängd ) hittats, och för potenserna 16 till 20, endast primitiva grupper hade hittats permutationer . För att söka efter primitiva grupper av högre grad utvecklade Charles Sims ett program som hittar ordning och viss struktur i en permutationsgrupp som ges av dess genereringsuppsättning [1] .

Det ursprungliga programmet som nämns i Sims papper skrevs för IBM 7040 vid Rutgers University och stödde alla grupper vars examen var mindre än 50 [7] . En exakt uppskattning av körtiden för en algoritm utfördes först av Furst, Hopcroft och Lax 1980 [8] . Löptiden förbättrades av Jerrum 1982 [9] och av Donald Knuth 1981 [10] . 1980 utvecklades en effektiv probabilistisk version av algoritmen [11] . Olika varianter av algoritmen, inklusive de som använder Schreier-vektorn istället för omloppsträdet, demonterades av Sheresh 2003 [12] [13] .

Inom beräkningsgruppteorin är algoritmer över permutationsgrupper ett av de mest utvecklade områdena, och än idag är de flesta av dessa algoritmer baserade på de metoder som Sims utvecklat [4] .

Huvudidé

Effektiviteten av beräkningar med en permutationsgrupp beror i huvudsak på hur den specificeras i programmet [2] . Ett effektivt sätt att göra detta är att isolera ett antal av dess undergrupper och välja unika coset för varje undergrupp i den serien i förhållande till dess föregångare. Algoritmen som föreslagits av Charles Sims hittar ett antal undergrupper där varje nästa grupp är stabilisatorn för den föregående. Sekvensen av punkter för vilka stabilisatorer är konstruerade kallas basen , och uppsättningen som innehåller genereringselementen för varje grupp i serien kallas den starka genereringsmängden [2] .

Algoritmen konstruerar en bas och en stark generatoruppsättning för permutationsundergruppen som ges av dess generatoruppsättning , med hjälp av Schreiers lemma för att hitta generatoruppsättningarna. Storleken på uppsättningarna som erhålls vid mellanliggande steg växer exponentiellt, därför har variationer av algoritmen utvecklats som minskar antalet övervägda genererande element [2] .

Representationen som beskrivs ovan delar upp en grupp i en produkt av delmängder kapslade i den, liknande hur stegrepresentationen delar upp ett vektorrum i en direkt summa av delutrymmen kapslade i det [3] .

Förklaring av problemet

En symmetrisk grupp är en grupp vars element är permutationer av element i någon uppsättning . Vanligtvis tas . som en sådan uppsättning . I en sådan notation kan elementen i en grupp ses som avbildningar som tar en uppsättning in i sig, det vill säga dess automorfismer . Gruppoperationen i sådan notation är sammansättningen av permutationer, för permutationer och definieras som , där för . Följaktligen kommer enhetspermutationen att vara en sådan permutation att , och den omvända permutationen kan ges som [14] . $S_{n}$ $\Omega$ $\Omega =\{1,2,\dots ,n\}$ $\sigma :\Omega \to \Omega$ $\Omega$ $\sigma_1$ $\sigma_2$ ${\displaystyle \sigma =\sigma _{1}\sigma _{2))$ $\sigma (\omega )=\sigma _{1}(\sigma _{2}(\omega ))$ $\omega \i \Omega$ $\sigma$ $\sigma (\omega )=\omega$ $\sigma ^{-1}(\sigma (\omega ))=\omega$

Låta vara uppsättningen av permutationer av längd . En genererad undergrupp av en mängd är den minsta genom inkludering undergruppen som innehåller som en undergrupp eller, ekvivalent, en undergrupp av alla element som kan representeras som en finit produkt av element och deras inverser. Ordningen för en permutationsgrupp är antalet element i den , och dess grad är kardinaliteten av den uppsättning som den verkar på. I sådan notation bör algoritmen kunna [7] : ${\displaystyle S=\{g_{1},\dots ,g_{m}\}\subset S_{n))$ $n$ $S$ $\langle S\rangle$ $S$ $S_{n}$ $S$ $S$ $|S|$ $|\Omega |$

Få ordningen på undergruppen som genereras av de givna permutationerna, ${\textstyle |\langle S\rangle |}$
Genom permutation , kontrollera om den ligger i den genererade undergruppen , $g$ $\langle S\rangle$
Lista sekventiellt elementen i den genererade undergruppen utan upprepning.

Applikationer

Algoritmändringar implementeras i de två mest populära datoralgebrasystemen som är specialiserade på beräkningsgruppteori - GAP och Magma [5] . Verktyg för att arbeta med permutationsgrupper, inklusive coset-uppräkningsalgoritmer och Schreier-Sims-algoritmen, är också tillgängliga i de mer allmänna populära systemen Maple och Mathematica [15] . Ursprungligen utvecklades algoritmen för att söka efter primitiva permutationsgrupper av en given grad [1] , men därefter har omfattningen av dess tillämpning vuxit många gånger - till exempel med denna algoritm kan du hitta lösningar på en given Rubiks kubkonfiguration , eftersom dess rotationer bildar en grupp [6] . Algoritmen visade sig också väl när man arbetade med matrisgrupper [16] .

Algoritm

Gruppfaktorisering

Låta vara en undergrupp av någon ändlig grupp , beteckna med transversal av familjen av vänster cosets . Alla element kan representeras unikt som , where och . Genom att successivt tillämpa detta resultat på och dess undergrupper kan det generaliseras i följande form [3] [17] : $H$ $G$ $G/H$ $\{gH:g\in G\}$ $g\in G$ $g=th$ $t\in G/H$ $h\in H$ $H$

Låt vara en serie av undergrupper . Då kan vilket element som helst representeras unikt som , där . ${\displaystyle G=G^{(0)}\geq G^{(1)}\geq \dots \geq G^{(k)}=\{e\))$ $G$ $g\in G$ ${\displaystyle g=g_{1}g_{2}\dots 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)}$

Beräknar ordning och listningselement

Vyn som beskrivs ovan har följande egenskaper:

Med Lagranges teorem kan ordningen för en grupp beräknas med formeln [3] , ${\textstyle |G|=|G^{(0)}/G^{(1)}|\times |G^{(1)}/G^{(2)}|\times \dots \times | G^{(k-1)}/G^{(k)}|}$
Elementen i en grupp kan räknas upp genom att räkna upp alla möjliga representationer [7] . ${\displaystyle g=g_{1}g_{2}\dots g_{k))$

För att även kunna kontrollera element för att tillhöra en genererad undergrupp är det nödvändigt att överväga serier av undergrupper av en speciell form, nämligen de som består av stabilisatorer [7] .

Banor och stabilisatorer

Låt agera på uppsättningen . Vi väljer en uppsättning element och konstruerar ett antal undergrupper så att var är elementets stabilisator . Med andra ord, är en undergrupp av element som översätter vart och ett av elementen till sig själv [7] . Med detta tillvägagångssätt, vid varje nästa steg, kommer den del av uppsättningen , på vilken nästa undergrupp icke-trivialt verkar , att minska med ett element, och ordningen för undergruppen med vilken arbetet utförs kommer att vara minst två gånger . Det följer av detta att iterationer av algoritmen kommer att krävas innan den önskade partitionen hittas [18] . $G$ $\Omega$ ${\textstil \omega _{1},\dots ,\omega _{k}\i \Omega }$ ${\textstil G^{(i)}=G_{\omega _{i}}^{(i-1)))$ ${\displaystyle G_{\omega }=\{g:g\omega =\omega \))$ $\omega$ ${\textstil G^{(i)))$ $G$ ${\textstil \omega _{1},\dots ,\omega _{i))$ $\Omega$ $G$ $\min(|\Omega |,\log |G|)$

För att konstruera cosets måste du använda det faktum att det finns en en-till-en-överensstämmelse (bijection) mellan elementen i omloppsbanan och de vänstra cosets av stabilisatorn [19] . $G\omega$ ${\textstyle G/G_{\omega ))$ ${\textstil G_{\omega ))$

Bevis

Enligt satsen om banor och stabilisatorer är uppsättningen av coset och omloppsbana ekvivalenta i kraft. Associera varje element med ett element i omloppsbanan . ${\displaystyle G/G_{\omega ))$ $G\omega$ ${\displaystyle t\in G/G_{\omega ))$ $t\omega$

Låt , då uppsättningarna och sammanfalla. Men av detta följer att också sammanfaller och : $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 ett ω = t ett ( G ω ω ) = ( t ett 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

Varje coset tilldelades exakt ett element i omloppsbanan. Eftersom tillbehören täcker hela gruppen är alla matchade element olika. Så det är verkligen en bijektion. ■ $G$

Det följer av beviset att man som representanter för coset kan ta element som realiserar olika punkter i omloppsbanan [19] . $G\omega$

Ägarkontroll

Beteckna med ett sådant element att . Om du delar upp i en serie stabilisatorer kan du kontrollera elementet för att tillhöra gruppen [7] : $\överlinje u$ ${\displaystyle G/G_{\omega ))$ ${\overline {u}}\omega =u$

Om , då det finns ett element så att , det vill säga , ${\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)))$
På grund av bijektionen mellan elementen i den intilliggande klassen och punkter i omloppsbanan, kan det entydigt fastställas att . $t_{i}={\overline {g(\omega _{i})}}$

Dessa egenskaper låter dig göra en övergång från till , vilket så småningom kommer att leda till att det aktuella elementet ska ligga i . Om detta verkligen är fallet, då är det möjligt att uttrycka [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}\dots t_{k))$

Banberäkning

Låt gruppen ha ett generatoraggregat . Banan för vilket element som helst under verkan av en grupp kan organiseras i ett träd av följande form [17] : $G$ $S$ $\alfa$ $G=\langle S\rangle$

Ett element skrivs vid roten av trädet , $\alpha \in \Omega$
Vid varje vertex av trädet skrivs något element från elementets bana , ${\textstil \beta \in G(\alpha )}$ $\alfa$
På kanten som leder från vertex med elementet till vertex med elementet finns ett element som . $u$ $v$ $s\i S$ $s(u)=v$

Det beskrivna trädet kan byggas genom en djup -första traversering, för detta är det nödvändigt att sortera genom elementet vid varje vertex tills det visar sig att en vertex ännu inte har allokerats för [17] . Implementeringsexempel i Python : $u$ $s\i S$ $s(u)$

# Bygger ett omloppsträd givet element w och genereringsmängd S def build_schreier_tree ( w , S , omloppsbana ): för g i S : om g [ w ] inte i omloppsbana : omlopp [ g [ w ]] = tillämpa ( g , omlopp [ w ]) build_schreier_tree ( g [ w ], S , orbit )

Här returnerar funktionen resultatet av att tillämpa gruppoperationen på elementen och som första och andra argument, och elementet lagras i . ${\mathsf {apply}}(a,b)$ $a$ $b$ ${\mathsf {omlopp}}[\alpha ]$ $\overline {\alpha }$

Schreiers Lemma

Det följer av Schreier-lemmat att stabilisatorn genereras av uppsättningen Schreier-generatorer: . Detta resultat tillåter oss att konstruera en genereringsmängd för från genereringsmängden för och elementets omloppsbana . Möjlig implementering för en funktion som returnerar en ny generatoruppsättning [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 )))$

# Tar en generatoruppsättning för G_{w-1} och en omloppsbana av w # Returnerar en generatoruppsättning för G_w def make_gen ( S , orbit ): n = len ( nästa ( iter ( S ))) newS = set () för s i S : för dig i omloppsbana : newS . lägg till ( reducera ( tillämpa , [ invers ( omlopp [ s [ u ] ] ), s , omlopp [ u ]])) returnera newS

Algoritmen är inte uttömd av detta, eftersom även om storleken på den nya genereringsmängden beror polynomiellt på storleken på omloppsbanan och den gamla genereringsmängden för ett enskilt anrop, sammanlagt för alla anrop till denna funktion, storleken på den genererande mängd växer exponentiellt [2] .

Sållningsgeneratorer

För att undvika okontrollerad tillväxt av generatoraggregat måste ett sållningsförfarande tillämpas . Detta skulle kräva följande uttalande [3] [20] :

Låt . Då är det möjligt att konstruera en uppsättning av högst element så att . $S\delmängd G$ $S'$ $\vert \Omega \vert ^{2}$ $\langle S'\rangle =\langle S\rangle$

Bevis

Låt oss först bevisa följande lemma:

Låt . Då ändras inte följande transformationer : $S\delmängd G$ $\langle S\rangle$

Ersättning för $s\i S$ $s^{{-1}}$
Ersätt med , var och $s\i S$ $st$ $t\in S$ $t\neq s$

Bevis

Låt, efter att ha tillämpat en av dessa operationer, vi får ett set . Det är uppenbart att . Å andra sidan kan dessa omvandlingar vändas genom omvandlingar av samma typ, så . Så . ■ $S'$ $S'\subset \langle S\rangle$ $S\subset \langle S'\rangle$ $\langle S\rangle =\langle S'\rangle$

Med hjälp av sådana transformationer kan vi reducera mängden till en sådan form att det för vilket par som helst i mängden finns högst ett element så att: $S$ $(I j)$ $s$

s ( ω ett ) = ω ett , s ( ω 2 ) = ω 2 , … , s ( ω i − ett ) = ω i − ett , s ( ω i ) = ω j ≠ ω i {\displaystyle s(\omega _{1})=\omega _{1},\ s(\omega _{2})=\omega _{2},\dots ,\ 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},\dots ,\ s(\omega _{i- 1})=\omega _{i-1},\ s(\omega _{i})=\omega _{j}\neq \omega _{i}

Detta kan uppnås genom att lägga till element i den nya uppsättningen en i taget och fortsätta på samma sätt som Gauss-metoden :

S'

Låt oss säga att vi vill lägga till ett nytt element , $S'$ $s$
Låt oss gå sekventiellt ${\displaystyle \omega _{1},\dots ,\omega _{n))$
1. Om , gå sedan till , ${\displaystyle s(\omega _{i})=\omega _{i))$ $\omega _{i+1}$
2. Om , kontrollera sedan om ett element med ett sådant par redan har påträffats , ${\displaystyle s(\omega _{i})=\omega _{j))$ $t$ $(I j)$
  1. Om vi träffades, ersätt sedan med och gå till , $s$ $s^{-1}t$ $\omega _{i+1}$
  2. Annars, kom ihåg vad som motsvarar paret och lägg till i den aktuella formen till , $s$ $(I j)$ $s$ $S'$
Om i slutet av algoritmen vi har , så ignorerar vi och ändrar inte . $s=e$ $s$ $S'$

Denna algoritm använder endast de elementära operationerna som anges ovan, därför . Observera att om , alltså , så är övergången till från i algoritmen korrekt, och varje par motsvarar faktiskt inte mer än en permutation. Med hänsyn till att det som mest finns sådana par , får vi det påstående som krävs.

■

\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}

Proceduren som beskrivs i beviset kallas Sims-filtret och fungerar i [21] . Dess implementering kan se ut så här: $O(|S|\cdot \Omega ^{2})$

# Tar en föräldrauppsättning S # Returnerar en förtunnad föräldrauppsättning S' def normalisera ( S ): n = len ( nästa ( iter ( S ))) newS = set () bas = [{} för i i intervallet ( n )] för s i S : för x i intervallet ( 0 , n ): om s [ x ] != x : om s [ x ] i basen [ x ]: s = tillämpas ( invers ( s ), bas [ x ][ s ] [ x ]]) annat : bas [ x ][ s [ x ]] = s newS . lägg till ( s ) bryt tillbaka nyS

Förutom Sims -filtret kan Jerrum-filtret [22] användas för att söka efter en liten uppsättning . Till skillnad från Sims-filtret, som hittar en uppsättning av högst element, hittar Jerrum-filtret en uppsättning av högst element. Samtidigt fungerar Jerrum-filtret för , så i fallet med Schreier-Sims-algoritmen är det att föredra att använda Sims-filtret [21] . $S'$ $|\Omega |^{2}$ $|\Omega |$ $O(|S|\cdot |\Omega |^{4})$

Algoritm

Allt ovanstående tillsammans ger en algoritm som kan implementeras kortfattat enligt följande [20] :

# Tar en genereringsmängd S = s1, ..., sk # Returnerar coset transversals U1, ..., Uk def schreier_sims ( S ): n = len ( nästa ( iter ( S ))) ans = [] w = 0 medan S : omloppsbana = {} omloppsbana [ w ] = tuppel ( intervall ( n )) build_schreier_tree ( w , S , omloppsbana ) ans += [[ omlopp [ i ] för i i omloppsbana ]] S = normalisera ( make_gen ( S , orbit )) w += 1 retur ans

Steg för steg har dess handlingar följande betydelse:

Elementets omloppsbana byggs av djup-först sökning, $\omega _{i}$
Alla Schreier-generatorer är beräknade för , ${\displaystyle G^{(i+1)))$
Många generatorer decimeras för att undvika deras exponentiella tillväxt.

Vid utgången kommer algoritmen att returnera en lista vars element är transversaler av coset . $G^{(0)}/G^{(1)},G^{(1)}/G^{(2)},\dots ,G^{(k-1)}/G^ {(k)}$

Körtid för algoritmen

Totalt kräver algoritmen inga fler iterationer. Varje iteration består av: $|\Omega |$

Att bygga ett omloppsträd som tar elementära operationer, $O(|S|\cdot |\Omega |)$
Konstruktionen av Schreier-generatorer, som tar elementär drift och returnerar generatorer, $O(|S|\cdot |\Omega |^{2})$ $|S|\cdot |\Omega |$
Normalisering av generatorset, som tar elementära operationer, där är uppsättningen som erhölls i föregående steg. $O(|S'|\cdot |\Omega |^{2})$ $S'$

Värdet i fallet när mängden ges ändras inte genom hela algoritmen och är lika med . Storleken på generatoraggregatet är initialt lika med , och överstiger inte vid varje efterföljande steg . Således kan den totala körtiden för algoritmen i implementeringen ovan uppskattas till [8] [12] [13] . $|\Omega |$ ${\displaystyle S=\{g_{1},\dots ,g_{m}\}\subset S_{n))$ $n$ $m$ $|\Omega |^{2}=n^{2}$ $O(n^{3}m+n^{6})$

Variationer av algoritmen

Pseudo-linjära versioner

Tidigare har det visat sig att algoritmen kräver iterationer. I det allmänna fallet kan storleken på gruppen vara i storleksordningen , och i det här fallet enligt Stirling-formeln , som uppenbarligen är större . Men i vissa fall är ordningen på gruppen liten, och därför är det mer lönsamt att ha en algoritm som beror på , och inte - till exempel, när det gäller någon känd grupp som ges som en permutationsgrupp [12] . $\min(|\Omega |,\log |G|)$ $n!$ $\log |G|\sim n\log n$ $|\Omega |=n$ $\log |G|$ $n$

Enligt Cayleys teorem är vilken ändlig grupp som helst isomorf till någon permutationsgrupp . Graden av en sådan grupp kan vara stor, men för många grupper är deras ordning sådan att . Till exempel är den dihedriska gruppen isomorf till permutationsgruppen som genereras av cyklisk förskjutning och reflektion . Det vill säga graden av denna grupp är , och ordningen är , och . För sådana grupper kan man överväga algoritmer med körtid , som kallas pseudolinjära [12] . $n$ $|G|$ $\log |G|<n$ $D_{n}$ $r=(1~~2~~\dots~~n)$ $s=(1~~n)(2~~n-1)(3~~n-2)\dots$ $n$ $2n$ $\log |G|\sim \log n$ $O(nm\log ^{c}|G|)$

I ett försök att föra algoritmen närmare en pseudo-linjär och minska graden , inkluderad i dess körtid, kom Sheresh till versioner av algoritmen som kräver [18] : $n$

$O(n^{2}\log ^{3}|G|+mn^{2}\log |G|)$ tid och minne $O(n^{2}\log |G|+mn)$
$O(n^{3}\log ^{3}|G|+mn^{3}\log |G|)$ tid och minne. $O(n\log ^{2}|G|+mn)$

Probabilistisk version

Den första fungerande probabilistiska versionen av algoritmen utvecklades av Jeffrey Leon 1980 [11] . Vanligtvis är det detta de menar när de talar om den probabilistiska Schreyer-Sims-metoden. I den, när man gallrade ut Schreier-generatorer, avslutades denna procedur i förtid om 20 generatorer i rad visade sig vara faktoriserade. Sheresh visade att, tillsammans med några optimeringar, ger denna procedur följande uttalande [5] :

För varje konstant finns det en algoritm av Monte Carlo-typ som, med en felsannolikhet på högst, kommer att konstruera en stark generatoruppsättning för permutationsgruppen med hjälp av tid och minne. $d$ ${\displaystyle n^{-d))$ $G=\langle S\rangle$ $O(n\log n\log ^{4}|G|+mn\log |G|)$ $O(n\log |G|+mn)$

I moderna datoralgebrasystem används vanligtvis modifieringar av denna version av algoritmen med olika heuristik för att påskynda programmet [5] .

Anteckningar

↑ 1 2 3 Sims, 1970 , sid. 169-170.
↑ 1 2 3 4 5 Murray, 2003 , sid. 1-3.
↑ 1 2 3 4 5 Holt, Eyck, O'Brien, 2005 , sid. 87-90.
↑ 1 2 Sheresh, 2003 , sid. 1-4.
↑ 1 2 3 4 Sheresh, 2003 , sid. 62-64.
↑ 1 2 Brouwer, 2016 , sid. fyra.
↑ 1 2 3 4 5 6 7 Sims, 1970 , sid. 176-177.
↑ 1 2 Furst, Hopcroft, Lax, 1980 .
↑ Jerrum, 1986 .
↑ Knuth, 1991 .
↑ 1 2 Leon, 1980 .
↑ 1 2 3 4 Sheresh, 2003 , sid. 48-54.
↑ 1 2 Holt, Eyck, O'Brien, 2005 , sid. 93-94.
↑ Zhuravlev, Flerov, Vyaly, 2019 , Permutations, sid. 31-36.
↑ Holt, Eyck, O'Brien, 2005 , sid. 1-7.
↑ Murray, O'Brien, 1995 .
↑ 1 2 3 Murray, 2003 , sid. 9-24.
↑ 1 2 Sheresh, 2003 , sid. 59-62.
↑ 1 2 Zhuravlev, Flerov, Vyaly, 2019 , Orbits and stabilizers, sid. 140-145.
↑ 1 2 3 Murray, 2003 , sid. 25-33.
↑ 1 2 Vipul Naik. Sims filter (engelska) . Groupprops, The Group Properties Wiki . Hämtad 23 september 2019. Arkiverad från originalet 1 september 2019.
↑ Vipul Naik. Jerrums filter . Groupprops, The Group Properties Wiki . Hämtad 19 september 2023. Arkiverad från originalet 1 september 2019.

Litteratur

Yu. I. Zhuravlev , Yu. A. Flerov och M. N. Vyaly Grunderna i högre algebra och kodningsteori . - FUPM MIPT, 2019. - S. 144. - 305 sid.
Charles C. Sims. Computational methods in the study of permutation groups (engelska) // 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 (engelska) . — New York: Chapman and Hall/CRC, 2005. — 536 sid. — ISBN 9780429147944 .
Merrick Furst, John Hopcroft, Eugene Luks. Polynom-tidsalgoritmer för permutationsgrupper (engelska) // 21st Annual Symposium on Foundations of Computer Science (sfcs 1980). - IEEE, 1980. - doi : 10.1109/sfcs.1980.34 .
Scott H. Murray. Schreier-Sims algorithm (engelska) // Institutionen för matematik, Australian National University. – 2003.
TC Brouwer. Lösa ett godtyckligt permutationspussel (engelska) // Mathematisch Instituut, Universiteit Leiden. — 2016.
Ákos Seress. Permutation Group Algorithms (engelska) // Cambridge Core. - 2003. - ISBN 9780511546549 . - doi : 10.1017/CBO9780511546549 .
Mark Jerrum. En kompakt representation för permutationsgrupper (engelska) // Journal of Algorithms. - 1986. - Vol. 7 , iss. 1 . — S. 60–78. — ISSN 0196-6774 . - doi : 10.1016/0196-6774(86)90038-6 .
Donald E. Knuth. Effektiv representation av permanentgrupper (engelska) // Combinatorica. - 1991. - Vol. 11 , iss. 1 . — S. 33–43. — ISSN 1439-6912 0209-9683, 1439-6912 . - doi : 10.1007/bf01375471 .
Jeffrey S. Leon På en algoritm för att hitta en bas och en stark genereringsmängd för en grupp som ges genom att generera permutationer // Mathematics of Computation. - 1980. - Vol. 35 , iss. 151 . - s. 941-974. — ISSN 0025-5718 . - doi : 10.1090/s0025-5718-1980-0572868-5 .
Scott H. Murray, EA O'Brien. Välja baspunkter för Schreier-Sims-algoritmen för matrisgrupper // Journal of Symbolic Computation. - 1995. - Vol. 19 , iss. 6 . - s. 577-584. — ISSN 0747-7171 . - doi : 10.1006/jsco.1995.1033 .

Gruppteori
Grundläggande koncept	Undergrupp Normal undergrupp Faktorgrupp Arbete direkt halvdirekt fri
Algebraiska egenskaper	kommutativ grupp Cyklisk grupp beställd grupp Förvandla grupp Lösbar grupp Schreiers Lemma Lagranges sats Sylows satser Klassificering av enkla ändliga grupper
ändliga grupper	Finit cyklisk grupp C n Symmetrisk grupp S n Dihedral grupp D n Alternerande grupp A n Klein Quadruple Group Mathieu-grupper M11 _ M12 _ M22 _ M23 _ M24 _ Conway grupper Co 1 Co2 _ Co3 _ Janko grupper J1 _ J2 _ J3 _ J4 _ Fisher grupper F22 _ F 23 F24 _ Monster (M)
Topologiska grupper	Lögngrupper Ortogonal grupp O(n) Special ortogonal grupp SO(n) Enhetsgrupp U(n) Särskild enhetlig grupp SU(n) Symplektisk grupp Sp(n) Exceptionellt enkelt Lorentz grupp Poincaré-gruppen
Algoritmer på grupper	Schreier - Sims Todd - Coxeter Fouriertransform