Schreier-Sims-algoritmi

Schreier-Sims-algoritmi
Earl Cayley -ryhmä $S_4$
Nimetty	Charles Sims ja Otto Schreyer
Tekijä	Charles Sims
tarkoitus	Permutaatioryhmän järjestyksen määrittäminen
Tietorakenne	Permutaatiot
pahin aika	$O(n^{3}m+n^{6})$

Schreier-Sims- algoritmi on laskennallisen ryhmäteorian alalta peräisin oleva algoritmi , jonka avulla yhden suorituksen jälkeen lineaarisessa ajassa voidaan löytää permutaatioiden muodostaman ryhmän järjestys , tarkistaa, kuuluuko elementti sellaiseen ryhmään ja luetella sen elementit. . Charles Sims ehdotti algoritmia vuonna 1970 primitiivisten permutaatioryhmien löytämiseksi [1] , ja se perustuu Schreierin alaryhmien sukupolven lemmaan [2] . Algoritmin löytämän permutaatioryhmän esitys on samanlainen kuin sen riviavaruuden matriisin askelmuoto [3] . Simsin kehittämät menetelmät muodostavat perustan useimmille nykyaikaisille algoritmeille työskentelyyn permutaatioryhmien kanssa [4] , algoritmin muunnelmia käytetään myös nykyaikaisissa tietokonealgebrajärjestelmissä , kuten GAP ja Magma [5] . Yksi algoritmin ilmeisimmistä sovelluksista on, että sitä voidaan käyttää Rubikin kuution ratkaisemiseen [6] .

Historia

Yksi permutaatioryhmien teorian pääongelmista on tietyn asteen permutaatioryhmien (eli joukon alkioiden vähimmäismäärän, jonka permutaatioryhmä sisältää tietyn permutaatioryhmän) etsiminen. Vuoteen 1970 mennessä tehoille 2 - 11 oli löydetty kaikki permutaatioryhmät, tehoille 12 - 15 kaikki transitiiviset ryhmät (eli alaryhmät, jotka toimivat transitiivisesti generaattorijoukossa ) ja tehoille 16 - 20 vain primitiiviset . ryhmille oli löydetty permutaatioita . Korkeamman asteen primitiivisten ryhmien etsimiseksi Charles Sims kehitti ohjelman, joka löytää järjestyksen ja rakenteen generointijoukon antamasta permutaatioryhmästä [1] .

Simsin paperissa mainittu alkuperäinen ohjelma kirjoitettiin Rutgersin yliopiston IBM 7040 :lle ja se tuki kaikkia ryhmiä, joiden tutkinto oli alle 50 [7] . Tarkan arvion algoritmin toiminta-ajasta tekivät ensimmäisen kerran Furst, Hopcroft ja Lax vuonna 1980 [8] . Ajoaikaa paransivat Jerrum vuonna 1982 [9] ja Donald Knuth vuonna 1981 [10] . Vuonna 1980 algoritmista kehitettiin tehokas probabilistinen versio [11] . Sheresh purki useita algoritmin muunnelmia, mukaan lukien ne, jotka käyttävät Schreier-vektoria kiertoratapuun sijaan, vuonna 2003 [12] [13] .

Laskennallisessa ryhmäteoriassa algoritmit permutaatioryhmien yli ovat yksi kehittyneimmistä alueista, ja nykyäänkin useimmat näistä algoritmeista perustuvat Simsin kehittämiin menetelmiin [4] .

Pääidea

Permutaatioryhmän laskelmien tehokkuus riippuu olennaisesti siitä, miten se on määritelty ohjelmassa [2] . Yksi tehokas tapa tehdä tämä on eristää useita sen alaryhmiä ja valita kullekin sarjan alaryhmälle ainutlaatuiset kosetit suhteessa edeltäjäänsä. Charles Simsin ehdottama algoritmi löytää useita alaryhmiä, joissa jokainen seuraava ryhmä on edellisen stabilaattori . Pisteiden sarjaa, joille stabilaattoreita rakennetaan, kutsutaan kantaluvuksi , ja sarjaa, joka sisältää generointielementit jokaiselle sarjan ryhmälle, kutsutaan vahvaksi generoivaksi joukoksi [2] .

Algoritmi rakentaa perustan ja vahvan generaattorijoukon sen generaattorijoukon antamalle permutaatioalaryhmälle käyttämällä Schreierin lemmaa löytääkseen generaattorijoukot. Välivaiheissa saatujen joukkojen koko kasvaa eksponentiaalisesti, joten algoritmille on kehitetty muunnelmia, jotka vähentävät tarkasteltavien generoivien elementtien määrää [2] .

Yllä kuvattu esitys jakaa ryhmän siihen sisäkkäisten osajoukkojen tuloksi, samalla tavalla kuin askelesitys jakaa vektoriavaruuden siihen sisäkkäisten aliavaruuksien suoraksi summaksi [3] .

Ongelman selvitys

Symmetrinen ryhmä on ryhmä, jonka alkiot ovat jonkin joukon alkioiden permutaatioita . Yleensä . pidetään sellaisena joukkona . Tällaisessa merkintätavassa ryhmän elementtejä voidaan pitää kartoitusina , jotka ottavat joukon itseensä, eli sen automorfismeina . Ryhmäoperaatio tällaisessa merkinnässä on permutaatioiden koostumus permutaatioille ja määritellään , missä for . Vastaavasti yksikköpermutaatio on sellainen permutaatio , että , ja käänteinen permutaatio voidaan antaa muodossa [14] . $S_{n}$ $\Omega$ ${\displaystyle \Omega =\{1,2,\pisteet ,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$

Antaa olla joukko permutaatioita pituus . Joukon generoitu aliryhmä on pienin inkluusio- aliryhmä , joka sisältää osajoukona tai vastaavasti aliryhmän kaikista alkioista , jotka voidaan esittää alkioiden ja niiden käänteisarvojen äärellisenä tulona. Permutaatioryhmän järjestys on siinä olevien elementtien lukumäärä ja sen aste on sen joukon kardinaliteetti, johon se vaikuttaa. Tällaisessa merkinnässä algoritmin pitäisi pystyä [7] : ${\displaystyle S=\{g_{1},\dots ,g_{m}\}\subset S_{n))$ $n$ $S$ $\langle S\rangle$ $S$ $S_{n}$ $S$ $S$ $|S|$ $|\Omega |$

Hanki annettujen permutaatioiden luoman aliryhmän järjestys , ${\textstyle |\langle S\rangle |}$
Tarkista permutaatiolla , kuuluuko se luotuun alaryhmään , $g$ $\langle S\rangle$
Listaa luodun aliryhmän elementit peräkkäin ilman toistoa.

Sovellukset

Algoritmien modifikaatioita on toteutettu kahdessa suosituimmassa laskennalliseen ryhmäteoriaan erikoistuneessa tietokonealgebrajärjestelmässä – GAP ja Magma [ [5] . Työkaluja permutaatioryhmien kanssa työskentelyyn, mukaan lukien kosetinlaskenta-algoritmit ja Schreier-Sims-algoritmi, on saatavilla myös yleisemmissä suosituissa järjestelmissä Maple ja Mathematica [15] . Aluksi algoritmi kehitettiin etsimään tietyn asteen primitiivisiä permutaatioryhmiä [1] , mutta myöhemmin sen sovellusalue on kasvanut moninkertaiseksi - esimerkiksi tällä algoritmilla voit löytää ratkaisuja tiettyyn Rubikin kuution kokoonpanoon , koska sen rotaatiot muodostavat ryhmän [6] . Lisäksi algoritmi osoitti itsensä hyvin matriisiryhmien kanssa työskennellessä [16] .

Algoritmi

Ryhmän faktorointi

Antaa olla alaryhmä joidenkin rajallinen ryhmä , joka tarkoittaa poikittainen perheen vasemmalle cosets . Mikä tahansa elementti voidaan yksilöllisesti esittää muodossa , missä ja . Soveltamalla tätä tulosta peräkkäin ja sen alaryhmiin se voidaan yleistää seuraavaan muotoon [3] [17] : $H$ $G$ $G/H$ $\{gH:g\in G\}$ $g\in G$ $g=th$ $t\in G/H$ $h\in H$ $H$

Antaa olla sarja alaryhmiä . Sitten mikä tahansa elementti voidaan esittää yksiselitteisesti muodossa , missä . ${\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)}$

Tilauksen laskeminen ja elementtien luettelointi

Yllä kuvatulla näkymällä on seuraavat ominaisuudet:

Lagrangen lauseen mukaan ryhmän järjestys voidaan laskea kaavalla [3] , ${\textstyle |G|=|G^{(0)}/G^{(1)}|\times |G^{(1)}/G^{(2)}|\times \dots \times | G^{(k-1)}/G^{(k)}|}$
Ryhmän elementit voidaan luetella luettelemalla kaikki mahdolliset esitykset [7] . ${\displaystyle g=g_{1}g_{2}\dots g_{k))$

Jotta voidaan myös tarkistaa elementtien kuuluvuus generoituun alaryhmään, on tarpeen ottaa huomioon sarja erikoismuotoisia alaryhmiä, nimittäin stabilaattoreista koostuvia [7] .

Radat ja stabilisaattorit

Anna toimia kuvauksissa . Valitsemme joukon elementtejä ja rakennamme useita aliryhmiä siten, että missä on elementin stabilisaattori . Toisin sanoen se on elementtien alaryhmä, joka kääntää jokaisen elementin itsestään [7] . Tällä lähestymistavalla kussakin seuraavassa vaiheessa joukon se osa , johon seuraava alaryhmä ei-triviaalisesti toimii , pienenee yhdellä elementillä ja sen alaryhmän järjestys, jonka kanssa työtä tehdään, on vähintään kaksinkertainen. . Tästä seuraa, että algoritmin iteraatioita tarvitaan ennen kuin haluttu osio löydetään [18] . $G$ $\Omega$ ${\textstyle \omega _{1},\dots ,\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},\dots ,\omega _{i))$ $\Omega$ $G$ $\min(|\Omega |,\log |G|)$

Kosettien muodostamiseen on käytettävä sitä tosiasiaa, että kiertoradan elementtien ja stabilisaattorin vasen kosettien välillä on yksi-yhteen vastaavuus (bijektio) [19] . $G\omega$ ${\textstyle G/G_{\omega }}$ ${\textstyle G_{\omega ))$

Todiste

Rata- ja stabilisaattoreita koskevan lauseen mukaan kosettien joukko ja rata ovat teholtaan ekvivalentteja. Yhdistä jokainen elementti kiertoradan elementtiin . ${\displaystyle G/G_{\omega ))$ $G\omega$ ${\displaystyle t\in G/G_{\omega ))$ $t\omega$

Anna sitten joukot ja osuvat yhteen. Mutta tästä seuraa, että myös samat ja : $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 yksi ω = t yksi ( G ω ω ) = ( t yksi 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

Jokaiselle kosetille määritettiin täsmälleen yksi kiertoradan elementti. Koska asusteet kattavat koko ryhmän , kaikki yhdistetyt elementit ovat erilaisia. Kyseessä on siis todellakin näkemys. ■ $G$

Todistuksesta seuraa, että kosettien edustajina voidaan ottaa elementtejä, jotka toteuttavat kiertoradan eri pisteet [19] . $G\omega$

Omistustarkistus

Merkitään sellaisella elementillä , että . Jakamalla stabilointisarjaan voit tarkistaa, kuuluuko elementti ryhmään [7] : $\overline u$ ${\displaystyle G/G_{\omega ))$ ${\overline {u}}\omega =u$

Jos , niin on elementti , joka on , ${\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)))$
Viereisen luokan elementtien ja kiertoradan pisteiden välisen bijektion perusteella voidaan yksiselitteisesti määrittää, että . $t_{i}={\overline {g(\omega _{i})}}$

Näiden ominaisuuksien avulla voit tehdä siirtymisen kohteesta , mikä johtaa lopulta siihen, että nykyisen elementin tulisi sijaita kohdassa . Jos näin todella on, niin , mistä on mahdollista ilmaista [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))$

Ratalaskenta

Anna ryhmälle generointisarja . Minkä tahansa ryhmän toiminnan alaisen elementin kiertorata voidaan järjestää seuraavan muotoiseksi puuksi [17] : $G$ $S$ $\alpha$ $G=\langle S\rangle$

Elementti kirjoitetaan puun juureen , $\alpha \in \Omega$
Puun jokaiseen kärkeen kirjoitetaan jokin elementti elementin kiertoradalta , ${\textstyle \beta \in G(\alpha )}$ $\alpha$
Elementin kärjestä elementin kärkeen johtavalla reunalla on sellainen elementti , että . $u$ $v$ $s\in S$ $s(u)=v$

Kuvattu puu voidaan rakentaa syvyys -first-läpikululla, tätä varten on tarpeen lajitella elementtiä kussakin kärjessä , kunnes käy ilmi, että [17] ei ole vielä varattu kärkeä . Toteutusesimerkki Pythonissa : $u$ $s\in S$ $s(u)$

# Muodostaa kiertoratapuun tietyllä elementillä w ja generoivalla joukolla S def build_schreier_tree ( w , S , orbit ): for g in S : if g [ w ] ei ole kiertoradalla : kiertorata [ g [ w ] ] = sovelletaan ( g , kiertorata [ w ]) build_schreier_tree ( g [ w ], S , orbit )

Tässä funktio palauttaa tuloksen ryhmäoperaation soveltamisesta elementteihin ja ensimmäisenä ja toisena argumenttina, ja elementti tallennetaan kohtaan . ${\mathsf {apply}}(a,b)$ $a$ $b$ ${\mathsf {orbit}}[\alpha ]$ $\overline {\alpha }$

Schreierin Lemma

Schreier-lemasta seuraa, että stabilisaattorin muodostaa joukko Schreier-generaattoreita: . Tämän tuloksen avulla voimme muodostaa generointijoukon for elementin generaattorijoukosta ja elementin radasta . Mahdollinen toteutus funktiolle, joka palauttaa uuden generointijoukon [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 )))$

# Ottaa generaattorijoukon G_{w-1} ja kiertoradan w # Palauttaa generaattorijoukon G_w def make_gen ( S , orbit ): n = len ( next ( iter ( S ))) newS = set () for s in S : for u in orbit : newS . add ( vähentää ( soveltaa , [ käänteinen ( kiertorata [ s [ u ]] ), s , kiertorata [ u ]])) return newS

Algoritmi ei tyhjene tässä, sillä vaikka uuden generaattorijoukon koko riippuu polynomiaalisesti kiertoradan koosta ja vanhasta generaattorijoukosta yhdelle yksittäiselle kutsulle, yhteenlaskettuna kaikkien tämän funktion kutsujen osalta generoivan joukon koko. joukko kasvaa eksponentiaalisesti [2] .

Seulontageneraattorit

Generaattorisarjojen hallitsemattoman kasvun välttämiseksi on käytettävä seulontamenettelyä . Tämä vaatisi seuraavan lausunnon [3] [20] :

Anna . Sitten on mahdollista rakentaa joukko enintään elementtejä siten, että . $S\alajoukko G$ $S'$ $\vert \Omega \vert ^{2}$ $\langle S'\rangle =\langle S\rangle$

Todiste

Todistetaan ensin seuraava lemma:

Anna . Sitten seuraavat muunnokset eivät muutu : $S\alajoukko G$ $\langle S\rangle$

Korvaava varten $s\in S$ $s^{{-1}}$
Korvataan , missä ja $s\in S$ $st$ $t\in S$ $t\neq s$

Todiste

Saavutetaan joukko . On selvää, että . Toisaalta nämä muunnokset voidaan peruuttaa samantyyppisillä muunnoksilla, joten . Joten . ■ $S'$ $S'\subset \langle S\rangle$ $S\subset \langle S'\rangle$ $\langle S\rangle =\langle S'\rangle$

Tällaisten muunnosten avulla voimme pienentää joukon sellaiseen muotoon, että mille tahansa joukon parille on enintään yksi alkio , joka: $S$ $(i,j)$ $s$

s ( ω yksi ) = ω yksi , s ( ω 2 ) = ω 2 , … , s ( ω i − yksi ) = ω i − yksi , 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}

Tämä voidaan saavuttaa lisäämällä elementtejä uuteen joukkoon yksi kerrallaan ja toimimalla samalla tavalla kuin Gaussin menetelmässä :

S'

Oletetaan, että haluamme lisätä uuden elementin , $S'$ $s$
Mennään peräkkäin ${\displaystyle \omega _{1},\dots ,\omega _{n))$
1. Jos , niin mene osoitteeseen , ${\displaystyle s(\omega _{i})=\omega _{i))$ $\omega _{i+1}$
2. Jos , niin tarkista onko elementti , jolla on tällainen pari , jo tavattu , ${\displaystyle s(\omega _{i})=\omega _{j))$ $t$ $(i,j)$
  1. Jos tapasimme, korvaa se ja siirry osoitteeseen $s$ $s^{-1}t$ $\omega _{i+1}$
  2. Muussa tapauksessa muista, mikä vastaa paria , ja lisää nykyiseen muotoon , $s$ $(i,j)$ $s$ $S'$
Jos algoritmin loppuun mennessä meillä on , jätämme huomioimatta emmekä muuta . $s=e$ $s$ $S'$

Tämä algoritmi käyttää vain yllä mainittuja perusoperaatioita, joten . Huomaa, että jos , niin , joten algoritmin siirtyminen kohteesta on oikea, ja jokainen pari vastaa itse asiassa enintään yhtä permutaatiota. Kun otetaan huomioon, että tällaisia pareja on enintään , saadaan vaadittu väite.

■

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

Todistuksessa kuvattua menettelyä kutsutaan Sims-suodattimeksi ja se toimii [21] . Sen toteutus saattaa näyttää tältä: $O(|S|\cdot \Omega ^{2})$

# Ottaa pääjoukon S # Palauttaa ohennetun kantajoukon S' def normalisoi ( S ) : n = len ( next ( iter ( S ))) newS = set () kanta = [{} for i alueella ( n )] s :lle S : lle x alueella ( 0 , n ) : jos s [ x ] ! = x : jos s [ x ] kantaosassa [ x ]: s = sovelletaan ( käänteinen ( s ) , kanta [ x ][ s [ x ]]) else : kanta [ x ][ s [ x ]] = s uutinenS . lisää ( t ) tauko paluu uutinenS

Sims- suodattimen lisäksi Jerrum-suodatinta [22] voidaan käyttää pienen sarjan etsimiseen . Toisin kuin Sims-suodatin, joka löytää joukon enintään elementtejä, Jerrum-suodatin löytää joukon enintään elementtejä. Samanaikaisesti Jerrum-suodatin toimii :lle , joten Schreier-Sims-algoritmin tapauksessa on suositeltavaa käyttää Sims-suodatinta [21] . $S'$ $|\Omega |^{2}$ $|\Omega |$ $O(|S|\cdot |\Omega |^{4})$

Algoritmi

Kaikki edellä mainitut yhdessä muodostavat algoritmin, joka voidaan toteuttaa ytimekkäästi seuraavasti [20] :

# Ottaa generointijoukon S = s1, ..., sk # Palauttaa coset transversaalit U1, ..., Uk def schreier_sims ( S ): n = len ( next ( iter ( S ))) ans = [] w = 0 kun taas S : kiertorata = {} kiertorata [ w ] = monikko ( alue ( n )) build_schreier_tree ( w , S , orbit ) ans += [[ orbit [ i ] for i in orbit ]] S = normalisoi ( make_gen ( S , orbit )) w += 1 paluu ans

Askel askeleelta sen toimilla on seuraava merkitys:

Elementin kiertorata rakennetaan syvähakulla, $\omega _{i}$
Kaikki Schreier-generaattorit on laskettu , ${\displaystyle G^{(i+1)))$
Monet generaattorit tuhoutuvat niiden eksponentiaalisen kasvun välttämiseksi.

Lähdössä algoritmi palauttaa listan, jonka elementit ovat kosettien poikittaissuuntauksia . $G^{(0)}/G^{(1)},G^{(1)}/G^{(2)},\dots ,G^{(k-1)}/G^ {(k)}$

Algoritmin ajoaika

Kaiken kaikkiaan algoritmi ei vaadi enempää iteraatioita. Jokainen iteraatio koostuu seuraavista: $|\Omega |$

Ratapuun rakentaminen, joka suorittaa perusoperaatioita, $O(|S|\cdot |\Omega |)$
Schreier-generaattoreiden rakentaminen, joka suorittaa perusoperaatioita ja palauttaa generaattoreita, $O(|S|\cdot |\Omega |^{2})$ $|S|\cdot |\Omega |$
Generointijoukon normalisointi, joka suorittaa alkeisoperaatioita, missä on edellisessä vaiheessa saatu joukko. $O(|S'|\cdot |\Omega |^{2})$ $S'$

Arvo siinä tapauksessa, että joukko annetaan , ei muutu algoritmin aikana ja on yhtä suuri kuin . Generointijoukon koko on alun perin yhtä suuri kuin , eikä missään seuraavassa vaiheessa ylitä . Näin ollen algoritmin kokonaisajoaika yllä olevassa toteutuksessa voidaan arvioida [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})$

Algoritmin muunnelmia

Pseudo-lineaariset versiot

Aikaisemmin on osoitettu, että algoritmi vaatii iteraatioita. Yleisessä tapauksessa ryhmän koko voi olla suuruusluokkaa , ja tässä tapauksessa Stirlingin kaavan mukaan, joka on selvästi suurempi . Mutta joissain tapauksissa ryhmän järjestys on pieni, ja siksi on kannattavampaa käyttää algoritmia, joka riippuu , eikä - esimerkiksi kun on kyse jostain tunnetusta ryhmästä, joka annetaan permutaatioryhmänä [12] . $\min(|\Omega |,\log |G|)$ $n!$ $\log |G|\sim n\log n$ $|\Omega |=n$ $\log |G|$ $n$

Cayleyn lauseen mukaan mikä tahansa äärellinen ryhmä on isomorfinen jollekin permutaatioryhmälle . Tällaisen ryhmän aste voi olla suuri, mutta monien ryhmien järjestys on sellainen, että . Esimerkiksi dihedraalinen ryhmä on isomorfinen syklisen siirron ja heijastuksen synnyttämälle permutaatioryhmälle . Eli tämän ryhmän aste on , ja järjestys on , ja . Tällaisille ryhmille voidaan harkita algoritmeja, joiden käyntiaika on , ja joita kutsutaan pseudolineaariseksi [12] . $n$ $|G|$ $\log |G|<n$ $D_{n}$ $r=(1~~2~~\pisteet~~n)$ $s=(1~~n)(2~~n-1)(3~~n-2)\pisteet$ $n$ $2n$ $\log |G|\sim \log n$ $O(nm\log ^{c}|G|)$

Yrittäessään tuoda algoritmia lähemmäksi pseudo-lineaarista ja pienentää sen ajoaikaan sisältyvää astetta Sheresh päätyi algoritmin versioihin, jotka vaativat [18] : $n$

$O(n^{2}\log ^{3}|G|+mn^{2}\log |G|)$ aikaa ja muistia $O(n^{2}\log |G|+mn)$
$O(n^{3}\log ^{3}|G|+mn^{3}\log |G|)$ aikaa ja muistia. $O(n\log ^{2}|G|+mn)$

Todennäköisyyspohjainen versio

Ensimmäisen toimivan todennäköisyyspohjaisen version algoritmista kehitti Jeffrey Leon vuonna 1980 [11] . Yleensä tätä he tarkoittavat puhuessaan todennäköisyydestä Schreyer-Sims -menetelmästä. Siinä, kun Schreier-generaattoreita harvennettiin, tämä menettely lopetettiin ennenaikaisesti, jos 20 generaattoria peräkkäin osoittautui tekijäksi. Sheresh osoitti, että yhdessä joidenkin optimointien kanssa tämä menettely antaa seuraavan lausuman [5] :

Jokaiselle vakiolle on olemassa Monte Carlo -tyyppinen algoritmi , joka korkeintaan virhetodennäköisyydellä rakentaa vahvan generaattorijoukon permutaatioryhmälle käyttämällä aikaa ja muistia. $d$ ${\näyttötyyli n^{-d))$ $G=\langle S\rangle$ $O(n\log n\log ^{4}|G|+mn\log |G|)$ $O(n\log |G|+mn)$

Nykyaikaisissa tietokonealgebrajärjestelmissä käytetään yleensä tämän algoritmin muunnelmia erilaisilla heuristikoilla nopeuttamaan ohjelmaa [5] .

Muistiinpanot

↑ 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. neljä.
↑ 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 , Permutaatiot, 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 , Radat ja stabilisaattorit, s. 140-145.
↑ 1 2 3 Murray, 2003 , s. 25-33.
↑ 1 2 Vipul Naik. Sims-suodatin (englanniksi) . Groupprops, The Group Properties Wiki . Haettu 23. syyskuuta 2019. Arkistoitu alkuperäisestä 1. syyskuuta 2019.
↑ Vipul Naik. Jerrumin suodatin . Groupprops, The Group Properties Wiki . Haettu 19. syyskuuta 2023. Arkistoitu alkuperäisestä 1. syyskuuta 2019.

Kirjallisuus

Yu. I. Zhuravlev , Yu. A. Flerov ja M. N. Vyaly Korkeamman algebran ja koodausteorian perusteet . - FUPM MIPT, 2019. - S. 144. - 305 s.
Charles C. Sims. Laskennalliset menetelmät permutaatioryhmien tutkimuksessa (englanniksi) // Computational Problems in Abstract Algebra. - Elsevier, 1970. - S. 176-177. — ISBN 9780080129754 .
Derek F. Holt, Bettina Eick, Eamonn A. O'Brien. Laskennallisen ryhmäteorian käsikirja (englanniksi) . — New York: Chapman ja Hall/CRC, 2005. — 536 s. — ISBN 9780429147944 .
Merrick Furst, John Hopcroft, Eugene Luks. Polynomiaikaiset algoritmit permutaatioryhmille (englanti) // 21st Annual Symposium on Foundations of Computer Science (sfcs 1980). - IEEE, 1980. - doi : 10.1109/sfcs.1980.34 .
Scott H. Murray. Schreier-Sims-algoritmi (englanti) // Matematiikan laitos, Australian National University. – 2003.
TC Brouwer. Satunnaisen permutaatiopulman ratkaiseminen (englanniksi) // Mathematisch Instituut, Universiteit Leiden. – 2016.
Ákos Seress. Permutaatioryhmäalgoritmit (englanniksi) // Cambridge Core. - 2003. - ISBN 9780511546549 . - doi : 10.1017/CBO9780511546549 .
Mark Jerrum. Kompakti esitys permutaatioryhmille (englanniksi) // Journal of Algorithms. - 1986. - Voi. 7 , iss. 1 . — s. 60–78. — ISSN 0196-6774 . - doi : 10.1016/0196-6774(86)90038-6 .
Donald E. Knuth. Perm-ryhmien tehokas esitys (englanti) // Combinatorica. - 1991. - Voi. 11 , iss. 1 . — s. 33–43. — ISSN 1439-6912 0209-9683, 1439-6912 . - doi : 10.1007/bf01375471 .
Jeffrey S. Leon Algoritmista perustan ja vahvan generointijoukon löytämiseksi ryhmälle, joka on annettu generoimalla permutaatioita // Laskennan matematiikka. - 1980. - Voi. 35 , iss. 151 . - s. 941-974. — ISSN 0025-5718 . - doi : 10.1090/s0025-5718-1980-0572868-5 .
Scott H. Murray, EA O'Brien. Peruspisteiden valitseminen Schreier-Sims-algoritmille matriisiryhmille // Journal of Symbolic Computation. - 1995. - Voi. 19 , iss. 6 . - s. 577-584. — ISSN 0747-7171 . - doi : 10.1006/jsco.1995.1033 .

Ryhmäteoria
Peruskonseptit	Alaryhmä Normaali alaryhmä Tekijäryhmä Työ suoraan puolisuorat vapaa
Algebralliset ominaisuudet	kommutatiivista ryhmää Syklinen ryhmä tilattu ryhmä Muutosryhmä Ratkaistava ryhmä Schreierin Lemma Lagrangen lause Sylowin lauseet Yksinkertaisten äärellisten ryhmien luokittelu
rajalliset ryhmät	Äärillinen syklinen ryhmä C n Symmetrinen ryhmä S n Dihedral ryhmä D n Vaihteleva ryhmä A n Kleinin neljän hengen ryhmä Mathieun ryhmät M11 _ M12 _ M22 _ M23 _ M24 _ Conway-ryhmät Yhteistyö 1 Co2_ _ Co3_ _ Jankon ryhmät J1_ _ J2_ _ J3_ _ J4_ _ Kalastajaryhmät F22 _ F 23 F24 _ Hirviö (M)
Topologiset ryhmät	Valheryhmät Ortogonaalinen ryhmä O(n) Erityinen ortogonaalinen ryhmä SO(n) Yhtenäinen ryhmä U(n) Erityinen yhtenäinen ryhmä SU(n) Symplektinen ryhmä Sp(n) Poikkeuksellisen yksinkertainen Lorentzin ryhmä Poincarén ryhmä
Algoritmit ryhmissä	Schreier - Sims Todd - Coxeter Fourier-muunnos