Schreier-Sims algoritme

Schreier-Sims algoritme
Earl Cayley Group $S_4$
Opkaldt efter	Charles Sims og Otto Schreyer
Forfatter	Charles Sims
formål	Bestemmelse af rækkefølgen af en permutationsgruppe
Datastruktur	Permutationer
værste tid	$O(n^{3}m+n^{6})$

Schreier-Sims- algoritmen er en algoritme fra området for beregningsgruppeteori, der tillader, efter en enkelt udførelse i lineær tid, at finde rækkefølgen af en gruppe genereret af permutationer, kontrollere om et element tilhører en sådan gruppe og opregne dets elementer . Algoritmen blev foreslået af Charles Sims i 1970 for at finde primitive permutationsgrupper [1] og er baseret på Schreiers undergruppegenerationslemma [2] . Repræsentationen af permutationsgruppen, som algoritmen finder, er analog med trinformen af matricen for densstrengmellemrum [3] . Metoderne udviklet af Sims danner grundlag for de fleste moderne algoritmer til at arbejde med permutationsgrupper [4] , modifikationer af algoritmen bruges også i moderne computeralgebrasystemer som GAP og Magma [5] . En af de mest oplagte anvendelser af algoritmen er, at den kan bruges til at løse Rubik's Cube [6] .

Historie

Et af hovedproblemerne i teorien om permutationsgrupper er søgningen efter permutationsgrupper af en given grad (det vil sige det mindste antal elementer i et sæt, hvis permutationsgruppe indeholder en given permutationsgruppe). I 1970 var alle permutationsgrupper blevet fundet for potenserne 2 til 11, for potenserne 12 til 15 var alle transitive grupper (det vil sige undergrupper, der virker transitivt på et generatorsæt ) fundet, og for potenserne 16 til 20 kun primitive grupper var blevet fundet permutationer . For at søge efter primitive grupper af højere grad udviklede Charles Sims et program, der finder orden og en vis struktur i en permutationsgruppe givet af dens generatorsæt [1] .

Det originale program nævnt i Sims' papir blev skrevet til IBM 7040 på Rutgers University og støttede enhver gruppe, hvis grad var mindre end 50 [7] . Et nøjagtigt estimat af køretiden for en algoritme blev først udført af Furst, Hopcroft og Lax i 1980 [8] . Løbetiden blev forbedret af Jerrum i 1982 [9] og af Donald Knuth i 1981 [10] . I 1980 blev der udviklet en effektiv probabilistisk version af algoritmen [11] . Forskellige variationer af algoritmen, inklusive dem, der bruger Schreier-vektoren i stedet for kredsløbstræet, blev demonteret af Sheresh i 2003 [12] [13] .

I beregningsgruppeteori er algoritmer over permutationsgrupper et af de mest udviklede områder, og selv i dag er de fleste af disse algoritmer baseret på metoderne udviklet af Sims [4] .

Hovedidé

Effektiviteten af beregninger med en permutationsgruppe afhænger i det væsentlige af, hvordan den er specificeret i programmet [2] . En effektiv måde at gøre dette på er at isolere et antal af dens undergrupper og vælge unikke cosets for hver undergruppe i den serie i forhold til dens forgænger. Algoritmen foreslået af Charles Sims finder et antal undergrupper, hvor hver næste gruppe er stabilisatoren af den forrige. Rækkefølgen af punkter, som stabilisatorer er konstrueret til, kaldes basen , og sættet, der indeholder de genererende elementer for hver gruppe i serien , kaldes det stærke generatorsæt [2] .

Algoritmen konstruerer en base og et stærkt generatorsæt for permutationsundergruppen givet af dens generatorsæt , ved at bruge Schreiers lemma til at finde generatorsættene. Størrelsen af de mængder, der opnås ved mellemliggende trin, vokser eksponentielt, derfor er der udviklet variationer af algoritmen, der reducerer antallet af overvejede genererende elementer [2] .

Den ovenfor beskrevne repræsentation opdeler en gruppe i et produkt af delmængder indlejret i den, svarende til hvordan trinrepræsentationen opdeler et vektorrum i en direkte sum af underrum indlejret i det [3] .

Udtalelse af problemet

En symmetrisk gruppe er en gruppe, hvis elementer er permutationer af elementer i et sæt . Normalt tages . som sådan et sæt . I en sådan notation kan elementerne i en gruppe ses som afbildninger , der tager et sæt ind i sig selv, det vil sige dets automorfismer . Gruppeoperationen i sådan notation er sammensætningen af permutationer, for permutationer og defineret som , hvor for . I overensstemmelse hermed vil enhedspermutationen være en permutation sådan, at , og den omvendte permutation kan gives som [14] . $S_{n}$ $\Omega$ ${\displaystyle \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$

Lade være sæt af permutationer af længde . En genereret undergruppe af et sæt er den mindste ved inklusion undergruppe , der indeholder som en undergruppe eller tilsvarende en undergruppe af alle elementer , der kan repræsenteres som et endeligt produkt af elementer og deres invers. Rækkefølgen af en permutationsgruppe er antallet af elementer i den , og dens grad er kardinaliteten af det sæt , som den virker på. I en sådan notation bør algoritmen være i stand til at [7] : ${\displaystyle S=\{g_{1},\dots ,g_{m}\}\subset S_{n))$ $n$ $S$ $\langle S\rangle$ $S$ $S_{n}$ $S$ $S$ $|S|$ $|\Omega |$

Få rækkefølgen af undergruppen genereret af de givne permutationer, ${\tekststil |\langle S\rangle |}$
Ved permutation skal du kontrollere, om den ligger i den genererede undergruppe , $g$ $\langle S\rangle$
List sekventielt elementerne i den genererede undergruppe uden gentagelse.

Ansøgninger

Algoritmeændringer er implementeret i de to mest populære computeralgebrasystemer, der er specialiseret i beregningsgruppeteori - GAP og Magma [5] . Værktøjer til at arbejde med permutationsgrupper, herunder coset-optællingsalgoritmer og Schreier-Sims-algoritmen, er også tilgængelige i de mere generelle populære systemer Maple og Mathematica [15] . Oprindeligt blev algoritmen udviklet til at søge efter primitive permutationsgrupper af en given grad [1] , men efterfølgende er omfanget af dens anvendelse vokset mange gange - for eksempel ved hjælp af denne algoritme kan du finde løsninger på en given Rubiks terningkonfiguration , da dens rotationer danner en gruppe [6] . Algoritmen viste sig også godt, når man arbejdede med matrixgrupper [16] .

Algoritme

Gruppefaktorisering

Lade være en undergruppe af nogle endelige gruppe , betegnes ved tværgående af familien af venstre cosets . Ethvert element kan være unikt repræsenteret som , hvor og . Ved successivt at anvende dette resultat til og dets undergrupper, kan det generaliseres i følgende form [3] [17] : $H$ $G$ $G/H$ ${\displaystyle \{gH:g\in G\))$ $g\in G$ $g=th$ $t\in G/H$ $h\in H$ $H$

Lad være en række undergrupper . Så kan ethvert element være unikt repræsenteret som , hvor . ${\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)}$

Beregning af rækkefølge og listeelementer

Visningen beskrevet ovenfor har følgende egenskaber:

Ved Lagranges sætning kan rækkefølgen af en gruppe beregnes ved hjælp af formlen [3] , ${\tekststil |G|=|G^{(0)}/G^{(1)}|\ gange |G^{(1)}/G^{(2)}|\ gange \dots \times | G^{(k-1)}/G^{(k)}|}$
Elementerne i en gruppe kan optælles ved at opregne alle mulige repræsentationer [7] . ${\displaystyle g=g_{1}g_{2}\dots g_{k))$

For også at kunne kontrollere elementer for at tilhøre en genereret undergruppe, er det nødvendigt at overveje serier af undergrupper af en speciel form, nemlig dem, der er sammensat af stabilisatorer [7] .

Baner og stabilisatorer

Lad handle på settet . Vi vælger et sæt af elementer og konstruerer et antal undergrupper, så hvor er elementets stabilisator . Med andre ord er en undergruppe af elementer , der oversætter hvert af elementerne til sig selv [7] . Med denne tilgang vil den del af sættet , som den næste undergruppe ikke-trivielt virker på, ved hvert næste trin falde med et element, og rækkefølgen af den undergruppe, som arbejdet udføres med, vil være mindst to gange . Det følger af dette, at iterationer af algoritmen vil være nødvendige, før den ønskede partition findes [18] . $G$ $\Omega$ ${\tekststil \omega _{1},\dots ,\omega _{k}\i \Omega }$ ${\textstyle G^{(i)}=G_{\omega _{i}}^{(i-1)))$ ${\displaystyle G_{\omega }=\{g:g\omega =\omega \))$ $\omega$ ${\tekststil G^{(i)))$ $G$ ${\tekststil \omega _{1},\dots ,\omega _{i))$ $\Omega$ $G$ $\min(|\Omega |,\log |G|)$

For at konstruere cosets skal du bruge det faktum, at der er en en-til-en overensstemmelse (bijection) mellem elementerne i kredsløbet og de venstre cosets af stabilisatoren [19] . $G\omega$ ${\textstyle G/G_{\omega ))$ ${\tekststil G_{\omega ))$

Bevis

Ved sætningen om baner og stabilisatorer er sættet af cosets og kredsløbet ækvivalente i kraft. Knyt hvert element til et element i kredsløbet . ${\displaystyle G/G_{\omega ))$ $G\omega$ ${\displaystyle t\in G/G_{\omega ))$ $t\omega$

Lad , så sæt og falde sammen. Men heraf følger, at det også er sammenfaldende og : $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 en ω = t en ( G ω ω ) = ( t en 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

Hvert coset blev tildelt nøjagtigt ét element i kredsløbet. Fordi cosets dækker hele gruppen , er alle matchede elementer forskellige. Så det er i sandhed en bijektion. ■ $G$

Det følger af beviset, at man som repræsentanter for cosets kan tage elementer, der realiserer forskellige punkter i kredsløbet [19] . $G\omega$

Ejerskabskontrol

Betegn med et sådant element , at . Opdeling i en række stabilisatorer giver dig mulighed for at kontrollere elementet for at tilhøre gruppen [7] : $\overline u$ ${\displaystyle G/G_{\omega ))$ ${\overline {u}}\omega =u$

Hvis , så er der et element sådan , det vil sige , ${\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)))$
I kraft af bijektionen mellem elementerne i den tilstødende klasse og kredsløbets punkter kan det entydigt bestemmes, at . $t_{i}={\overline {g(\omega _{i})}}$

Disse egenskaber giver dig mulighed for at lave en overgang fra til , hvilket i sidste ende vil føre til, at det aktuelle element skal ligge i . Hvis dette virkelig er tilfældet, så , hvorfra er det muligt at udtrykke [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))$

Baneberegning

Lad gruppen have et generatorsæt . Banen for ethvert element under påvirkning af en gruppe kan organiseres i et træ med følgende form [17] : $G$ $S$ $\alfa$ $G=\langle S\rangle$

Et element er skrevet ved roden af træet , $\alpha \in \Omega$
Ved hvert hjørne af træet er der skrevet et element fra elementets bane , ${\tekststil \beta \i G(\alpha )}$ $\alfa$
På kanten, der fører fra toppunktet med elementet til toppunktet med elementet , er der et element sådan, at . $u$ $v$ $s\i S$ $s(u)=v$

Det beskrevne træ kan bygges ved en dybde -første traversering, for dette er det nødvendigt at sortere gennem elementet ved hvert toppunkt , indtil det viser sig, at der endnu ikke er allokeret et toppunkt for [17] . Implementeringseksempel i Python : $u$ $s\i S$ $s(u)$

# Opbygger et kredsløbstræ givet element w og genereringssæt S def build_schreier_tree ( w , S , kredsløb ): for g i S : hvis g [ w ] ikke er i kredsløb : kredsløb [ g [ w ]] = gælder ( g , kredsløb [ w ]) build_schreier_tree ( g [ w ], S , orbit )

Her returnerer funktionen resultatet af at anvende gruppeoperationen på elementerne og som første og andet argument, og elementet gemmes i . ${\mathsf {anvend}}(a,b)$ $-en$ $b$ ${\mathsf {orbit}}[\alpha ]$ $\overline {\alpha }$

Schreiers Lemma

Det følger af Schreier-lemmaet, at stabilisatoren genereres af sættet af Schreier-generatorer: . Dette resultat giver os mulighed for at konstruere et generatorsæt for ud fra generatorsættet for og elementets kredsløb . Mulig implementering af en funktion, der returnerer et nyt generatorsæt [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 )))$

# Tager et generatorsæt for G_{w-1} og en kredsløb på w # Returnerer et generatorsæt for G_w def make_gen ( S , orbit ): n = len ( næste ( iter ( S ))) newS = sæt () for s i S : for u i kredsløb : newS . tilføje ( reducere ( anvende , [ omvendt ( kredsløb [ s [ u ] ] ), s , kredsløb [ u ]])) returnere newS

Algoritmen er ikke udtømt af dette, da selv om størrelsen af det nye generatorsæt polynomielt afhænger af størrelsen af kredsløbet og det gamle generatorsæt for et enkelt opkald, er størrelsen af den genererende funktion samlet for alle kald til denne funktion. mængde vokser eksponentielt [2] .

Sigtningsgeneratorer

For at undgå ukontrolleret vækst af generatorsæt skal der anvendes en sigteprocedure . Dette ville kræve følgende erklæring [3] [20] :

Lad . Så er det muligt at konstruere et sæt af højst elementer sådan, at . $S\undersæt G$ $S'$ $\vert \Omega \vert ^{2}$ $\langle S'\rangle =\langle S\rangle$

Bevis

Lad os først bevise følgende lemma:

Lad . Så ændres følgende transformationer ikke : $S\undersæt G$ $\langle S\rangle$

Erstatning for $s\i S$ $s^{{-1}}$
Udskiftning med , hvor og $s\i S$ $st$ $t\in S$ $t\neq s$

Bevis

Lad, efter at have anvendt en af disse operationer, vi får et sæt . Det er indlysende . På den anden side kan disse konverteringer vendes ved konverteringer af samme type, så . Så . ■ $S'$ $S'\subset \langle S\rangle$ $S\subset \langle S'\rangle$ $\langle S\rangle =\langle S'\rangle$

Ved hjælp af sådanne transformationer kan vi reducere sættet til en sådan form, at der for ethvert par i sættet højst er ét element, således at: $S$ $(i,j)$ $s$

s ( ω en ) = ω en , s ( ω 2 ) = ω 2 , … , s ( ω jeg − en ) = ω jeg − en , s ( ω jeg ) = ω j ≠ ω jeg {\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}

Dette kan opnås ved at tilføje elementer til det nye sæt et ad gangen og fortsætte på samme måde som Gauss-metoden :

S'

Lad os sige, at vi vil tilføje et nyt element , $S'$ $s$
Lad os gå sekventielt ${\displaystyle \omega _{1},\dots ,\omega _{n))$
1. Hvis , så gå til , ${\displaystyle s(\omega _{i})=\omega _{i))$ $\omega _{i+1}$
2. Hvis , så tjek om et element med et sådant par allerede er stødt på , ${\displaystyle s(\omega _{i})=\omega _{j))$ $t$ $(i,j)$
  1. Hvis vi mødtes, så erstat med og gå til , $s$ $s^{-1}t$ $\omega _{i+1}$
  2. Ellers skal du huske, hvad der svarer til parret , og tilføje i den aktuelle form til , $s$ $(i,j)$ $s$ $S'$
Hvis vi ved udgangen af den algoritme, vi har , ignorerer vi og ændrer ikke . $s=e$ $s$ $S'$

Denne algoritme bruger derfor kun de elementære operationer angivet ovenfor . Bemærk, at hvis , så , så overgangen til fra i algoritmen er korrekt, og hvert par svarer faktisk ikke til mere end én permutation. Under hensyntagen til, at der højst er sådanne par , opnår vi den nødvendige påstand.

■

\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 beskrevet i beviset kaldes Sims-filteret og fungerer i [21] . Dens implementering kan se sådan ud: $O(|S|\cdot \Omega ^{2})$

# Tager et overordnet sæt S # Returnerer et fortyndet overordnet sæt S' def normalisere ( S ): n = len ( næste ( iter ( S ))) newS = sæt () base = [{} for i i området ( n )] for s i S : for x i området ( 0 , n ): hvis s [ x ] != x : hvis s [ x ] i base [ x ] : s = gælder ( omvendt ( s ), base [ x ][ s ] [ x ]]) andet : base [ x ][ s [ x ]] = s newS . tilføje ( r ) bryde returnere nyS

Ud over Sims -filteret kan Jerrum-filteret [22] bruges til at søge efter et lille sæt . I modsætning til Sims-filteret, som finder et sæt af højst elementer, finder Jerrum-filteret et sæt af højst elementer. Samtidig virker Jerrum-filteret for , så i tilfælde af Schreier-Sims-algoritmen er det at foretrække at bruge Sims-filteret [21] . $S'$ $|\Omega |^{2}$ $|\Omega |$ $O(|S|\cdot |\Omega |^{4})$

Algoritme

Alt ovenstående giver tilsammen en algoritme, der kortfattet kan implementeres som følger [20] :

# Tager et generatorsæt S = s1, ..., sk # Returnerer coset transversals U1, ..., Uk def schreier_sims ( S ): n = len ( næste ( iter ( S ))) ans = [] w = 0 mens S : kredsløb = {} kredsløb [ w ] = tupel ( område ( n )) build_schreier_tree ( w , S , kredsløb ) og += [[ kredsløb [ i ] for i i kredsløb ]] S = normalisere ( make_gen ( S , kredsløb )) w += 1 retur ans

Trin for trin har dens handlinger følgende betydning:

Elementets kredsløb bygges ved dybde-først søgning, $\omega _{i}$
Alle Schreier generatorer er beregnet til , ${\displaystyle G^{(i+1)))$
Mange generatorer decimeres for at undgå deres eksponentielle vækst.

Ved udgangen vil algoritmen returnere en liste, hvis elementer er tværgående af cosets . $G^{(0)}/G^{(1)},G^{(1)}/G^{(2)},\dots ,G^{(k-1)}/G^ {(k)}$

Køretid for algoritmen

I alt kræver algoritmen ikke flere iterationer. Hver iteration består af: $|\Omega |$

At bygge et kredsløbstræ, der tager elementære operationer, $O(|S|\cdot |\Omega |)$
Konstruktionen af Schreier-generatorer, som tager elementær drift og returnerer generatorer, $O(|S|\cdot |\Omega |^{2})$ $|S|\cdot |\Omega |$
Normalisering af generatorsættet, som tager elementære operationer, hvor er sættet opnået i det foregående trin. $O(|S'|\cdot |\Omega |^{2})$ $S'$

Værdien i det tilfælde, hvor sættet er givet , ændres ikke gennem hele algoritmen og er lig med . Størrelsen af generatorsættet er initialt lig med , og overstiger ved hvert efterfølgende trin ikke . Således kan den samlede køretid for algoritmen i ovenstående implementering estimeres til [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 af algoritmen

Pseudo-lineære versioner

Tidligere har det vist sig, at algoritmen kræver iterationer. I det generelle tilfælde kan størrelsen af gruppen være af størrelsesordenen , og i dette tilfælde ifølge Stirling-formlen , som naturligvis er større . Men i nogle tilfælde er rækkefølgen af gruppen lille, og derfor er det mere rentabelt at have en algoritme, der afhænger af , og ikke - for eksempel, når det drejer sig om en kendt gruppe, der er angivet som en permutationsgruppe [12] . $\min(|\Omega |,\log |G|)$ $n!$ $\log |G|\sim n\log n$ $|\Omega |=n$ $\log |G|$ $n$

Ved Cayleys sætning er enhver endelig gruppe isomorf til en eller anden permutationsgruppe . Graden af en sådan gruppe kan være stor, men for mange grupper er deres rækkefølge sådan, at . For eksempel er den dihedrale gruppe isomorf til permutationsgruppen genereret af cyklisk skift og refleksion . Det vil sige, at graden af denne gruppe er , og rækkefølgen er , og . For sådanne grupper kan man overveje algoritmer med køretid , som kaldes pseudo-lineære [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 et forsøg på at bringe algoritmen tættere på en pseudo-lineær og reducere graden , inkluderet i dens køretid, kom Sheresh til versioner af algoritmen, der kræver [18] : $n$

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

Probabilistisk version

Den første fungerende probabilistiske version af algoritmen blev udviklet af Jeffrey Leon i 1980 [11] . Normalt er det det, de mener, når de taler om den probabilistiske Schreyer-Sims-metode. Ved udtynding af Schreier-generatorer blev denne procedure afsluttet for tidligt, hvis 20 generatorer i træk viste sig at være faktoriseret. Sheresh viste, at denne procedure sammen med nogle optimeringer giver følgende erklæring [5] :

For enhver konstant er der en Monte Carlo-type algoritme , der med en fejlsandsynlighed på højst vil konstruere et stærkt generatorsæt for permutationsgruppen ved hjælp af tid og hukommelse. $d$ ${\displaystyle n^{-d))$ $G=\langle S\rangle$ $O(n\log n\log ^{4}|G|+mn\log |G|)$ $O(n\log |G|+mn)$

I moderne computeralgebrasystemer bruges modifikationer af denne version af algoritmen med forskellige heuristika normalt til at fremskynde programmet [5] .

Noter

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

Litteratur

Yu. I. Zhuravlev , Yu. A. Flerov og M. N. Vyaly Grundlæggende om højere algebra og kodningsteori . - FUPM MIPT, 2019. - S. 144. - 305 s.
Charles C. Sims. Beregningsmetoder i studiet af permutationsgrupper (engelsk) // 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 (engelsk) . — New York: Chapman og Hall/CRC, 2005. — 536 s. — ISBN 9780429147944 .
Merrick Furst, John Hopcroft, Eugene Luks. Polynomial-time algoritmer for permutationsgrupper (engelsk) // 21st Annual Symposium on Foundations of Computer Science (sfcs 1980). - IEEE, 1980. - doi : 10.1109/sfcs.1980.34 .
Scott H. Murray. Schreier-Sims algoritme (engelsk) // Institut for matematik, Australian National University. – 2003.
TC Brouwer. Løsning af et vilkårligt permutationspuslespil (engelsk) // Mathematisch Instituut, Universiteit Leiden. – 2016.
Ákos Seress. Permutationsgruppealgoritmer (engelsk) // Cambridge Core. - 2003. - ISBN 9780511546549 . - doi : 10.1017/CBO9780511546549 .
Mark Jerrum. En kompakt repræsentation for permutationsgrupper (engelsk) // Journal of Algorithms. - 1986. - Bd. 7 , iss. 1 . — S. 60–78. — ISSN 0196-6774 . - doi : 10.1016/0196-6774(86)90038-6 .
Donald E. Knuth. Effektiv repræsentation af perm-grupper (engelsk) // Combinatorica. - 1991. - Bd. 11 , iss. 1 . — S. 33–43. — ISSN 1439-6912 0209-9683, 1439-6912 . - doi : 10.1007/bf01375471 .
Jeffrey S. Leon På en algoritme til at finde en base og et stærkt generatorsæt for en gruppe givet ved at generere permutationer // Mathematics of Computation. - 1980. - Bd. 35 , iss. 151 . - s. 941-974. — ISSN 0025-5718 . - doi : 10.1090/s0025-5718-1980-0572868-5 .
Scott H. Murray, EA O'Brien. Valg af basispunkter for Schreier-Sims-algoritmen for matrixgrupper // Journal of Symbolic Computation. - 1995. - Bd. 19 , iss. 6 . - S. 577-584. — ISSN 0747-7171 . - doi : 10.1006/jsco.1995.1033 .

Gruppeteori
Basale koncepter	Undergruppe Normal undergruppe Faktor gruppe Arbejde direkte semi-direkte ledig
Algebraiske egenskaber	kommutativ gruppe Cyklisk gruppe bestilt gruppe Forvandle gruppe Opløselig gruppe Schreiers Lemma Lagranges sætning Sylows sætninger Klassificering af simple endelige grupper
begrænsede grupper	Endelig cyklisk gruppe C n Symmetrisk gruppe S n Dihedral gruppe D n Skiftende gruppe A n Klein Quadruple Group Mathieu grupper M11 _ M12 _ M22 _ M23 _ M24 _ Conway grupper Co 1 Co2 _ Co3 _ Janko grupper J1 _ J2 _ J3 _ J4 _ Fiskergrupper F22 _ F 23 F24 _ Monster (M)
Topologiske grupper	Løgngrupper Ortogonal gruppe O(n) Særlig ortogonal gruppe SO(n) Enhedsgruppe U(n) Særlig enhedsgruppe SU(n) Symplektisk gruppe Sp(n) Enestående enkel Lorentz gruppe Poincaré gruppe
Algoritmer på grupper	Schreier - Sims Todd - Coxeter Fourier transformation