Schreier-Sims algoritmus

Schreier-Sims algoritmus
Earl Cayley csoport $S_4$
Valaki után elnevezve	Charles Sims és Otto Schreyer
Szerző	Charles Sims
célja	Permutációs csoport sorrendjének meghatározása
Adatstruktúra	Permutációk
legrosszabb idő	$O(n^{3}m+n^{6})$

A Schreier-Sims algoritmus a számítási csoportelmélet területéről származó algoritmus , amely lehetővé teszi, hogy egyetlen végrehajtás után lineáris időben megtaláljuk a permutációk által generált csoport sorrendjét , ellenőrizzük, hogy egy elem egy ilyen csoportba tartozik-e, és felsoroljuk az elemeit. . Az algoritmust Charles Sims javasolta 1970-ben primitív permutációs csoportok keresésére [1] , és Schreier alcsoportgenerálási lemmáján [2] alapul . Az algoritmus által talált permutációs csoport reprezentációja hasonló a mátrix lépésformájához a sorterére [3] . A Sims által kifejlesztett módszerek képezik a legtöbb permutációs csoportokkal való munkavégzés modern algoritmusának alapját [4] , az algoritmus módosításait olyan modern számítógépes algebrai rendszerekben is alkalmazzák, mint a GAP és a Magma [5] . Az algoritmus egyik legkézenfekvőbb alkalmazása, hogy a Rubik-kocka megoldására használható [6] .

Történelem

A permutációs csoportok elméletének egyik fő problémája az adott fokú permutációs csoportok keresése (vagyis egy halmaz elemeinek minimális száma, amelynek permutációs csoportja egy adott permutációs csoportot tartalmaz). 1970-re a 2-től 11-ig terjedő hatványokhoz az összes permutációs csoportot megtalálták, a 12-től 15-ig terjedő hatványokhoz az összes tranzitív csoportot (vagyis a generátorkészleten tranzitívan ható alcsoportokat ), a 16-tól 20-ig terjedő hatványokhoz pedig csak primitív csoportokat találtak. csoportok permutációit találtak . A magasabb fokú primitív csoportok keresésére Charles Sims kifejlesztett egy programot, amely rendet és valamilyen struktúrát talál a generátorkészlete által megadott permutációs csoportban [1] .

A Sims cikkében említett eredeti program az IBM 7040 számára készült a Rutgers Egyetemen , és minden olyan csoportot támogatott, akiknek végzettsége 50 alatt volt [7] . Egy algoritmus futási idejének pontos becslését először Furst, Hopcroft és Lax végezte el 1980-ban [8] . A futási időt Jerrum 1982-ben [9] és Donald Knuth 1981-ben [10] javította . 1980-ban kidolgozták az algoritmus hatékony valószínűségi változatát [11] . Az algoritmus különféle változatait, köztük azokat, amelyek a pályafa helyett a Schreier-vektort használják, Sheresh 2003- ban leszerelte [12] [13] .

A számítási csoportelméletben a permutációs csoportok feletti algoritmusok az egyik legfejlettebb terület, és még ma is ezeknek az algoritmusoknak a többsége a Sims által kidolgozott módszereken alapul [4] .

Fő ötlet

A permutációs csoporttal végzett számítások hatékonysága alapvetően attól függ, hogyan van megadva a programban [2] . Ennek egyik hatékony módja az, hogy számos alcsoportját elkülönítjük, és a sorozat minden egyes alcsoportjához egyedi koseteket választunk az elődhöz képest. A Charles Sims által javasolt algoritmus számos olyan alcsoportot talál, amelyekben minden következő csoport az előző stabilizátora . Azt a pontsorozatot, amelyre stabilizátorokat készítenek, bázisnak nevezzük , a sorozat egyes csoportjaihoz tartozó generáló elemeket tartalmazó halmazt pedig erős generáló halmaznak [2] .

Az algoritmus létrehoz egy bázist és egy erős generátorkészletet a generátorkészlete által megadott permutációs alcsoporthoz , Schreier lemmáját felhasználva a generátorkészletek megtalálásához. A közbenső lépésekben kapott halmazok mérete exponenciálisan növekszik, ezért az algoritmusnak olyan változatait fejlesztették ki, amelyek csökkentik a figyelembe vett generáló elemek számát [2] .

A fent leírt reprezentáció feloszt egy csoportot a benne beágyazott részhalmazok szorzatára, hasonlóan ahhoz, ahogy a lépéses reprezentáció a vektorteret a benne beágyazott alterek közvetlen összegére hasítja [3] .

A probléma leírása

A szimmetrikus csoport olyan csoport, amelynek elemei valamely halmaz elemeinek permutációi . Általában a .-t ilyen halmaznak tekintik . Ebben a jelölésben egy csoport elemeit leképezéseknek tekinthetjük, amelyek magukba foglalnak egy halmazt , vagyis annak automorfizmusait . Az ilyen jelölésben szereplő csoportművelet a permutációk összetétele a permutációkhoz, és definíciója: , ahol for . Ennek megfelelően az egységpermutáció olyan permutáció lesz , hogy , és a fordított permutáció megadható [14] . $S_{n}$ $\Omega$ $\Omega =\{1,2,\pontok ,n\}$ $\sigma :\Omega \to \Omega$ $\Omega$ $\sigma_1$ $\sigma_2$ ${\displaystyle \sigma =\sigma _{1}\sigma _{2))$ $\sigma (\omega )=\sigma _{1}(\sigma _{2}(\omega ))$ $\omega \az \Omegában$ $\sigma$ $\sigma (\omega )=\omega$ $\sigma ^{-1}(\sigma (\omega ))=\omega$

Legyen a hosszúságú permutációk halmaza . Egy halmaz generált alcsoportja a legkisebb befoglalási alcsoport , amely részhalmazként vagy ennek megfelelő módon az elemek és inverzeik véges szorzataként ábrázolható összes elem alcsoportját tartalmazza. Egy permutációs csoport sorrendje a benne lévő elemek száma, foka pedig annak a halmaznak a kardinalitása, amelyre hat. Ilyen jelölés esetén az algoritmusnak képesnek kell lennie [7] : ${\displaystyle S=\{g_{1},\dots ,g_{m}\}\subset S_{n))$ $n$ $S$ $\langle S\rangle$ $S$ $S_{n}$ $S$ $S$ $|S|$ $|\Omega |$

Szerezd meg a megadott permutációk által generált alcsoport sorrendjét , ${\textstyle |\langle S\rangle |}$
Permutációval ellenőrizze , hogy a generált alcsoportban van - e , $g$ $\langle S\rangle$
Sorban , ismétlés nélkül sorolja fel a generált alcsoport elemeit.

Alkalmazások

Az algoritmusmódosításokat a két legnépszerűbb , számítási csoportelméletre szakosodott számítógépes algebra rendszerben – a GAP -ban és a Magmában [5] valósítják meg . A permutációs csoportokkal való munkavégzésre szolgáló eszközök, beleértve a kosetfelsorolási algoritmusokat és a Schreier-Sims algoritmust, szintén elérhetők a népszerűbb Maple és Mathematica rendszerekben [15] . Kezdetben az algoritmust egy adott fokú primitív permutációs csoportok keresésére fejlesztették ki [1] , de később az alkalmazási köre sokszorosára nőtt – például ezzel az algoritmussal lehet megoldásokat találni egy adott Rubik-kocka konfigurációra . mivel forgásai egy csoportot alkotnak [6] . Ezenkívül az algoritmus jól mutatkozott a mátrixcsoportokkal végzett munka során [16] .

Algoritmus

Csoportfaktorizálás

Legyen valamilyen véges csoport részcsoportja , amelyet a bal oldali kosettek családjának keresztirányával jelölünk . Bármely elem egyedileg ábrázolható , hol és . Ha ezt az eredményt egymás után alkalmazzuk alcsoportjaira, az alábbi formában általánosítható [3] [17] : $H$ $G$ $G/H$ $\{gH:g\in G\}$ $g\in G$ $g=th$ $t\in G/H$ $h\in H$ $H$

Legyen alcsoportok sorozata . Ekkor bármely elem egyedileg ábrázolható , ahol . ${\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)}$

Sorrend kiszámítása és elemek listázása

A fent leírt nézet a következő tulajdonságokkal rendelkezik:

A Lagrange-tétel alapján egy csoport sorrendje kiszámítható a [3] képlet segítségével , ${\textstyle |G|=|G^{(0)}/G^{(1)}|\times |G^{(1)}/G^{(2)}|\times \dots \times | G^{(k-1)}/G^{(k)}|}$
Egy csoport elemei az összes lehetséges reprezentáció felsorolásával felsorolhatók [7] . ${\displaystyle g=g_{1}g_{2}\dots g_{k))$

Ahhoz, hogy egy generált alcsoporthoz tartozó elemeket is ellenőrizhessük, speciális formájú alcsoportok sorozatát kell figyelembe venni, nevezetesen a stabilizátorokból állókat [7] .

Pályák és stabilizátorok

Hadd cselekedjen a forgatáson . Kiválasztunk egy elemhalmazt, és számos alcsoportot alkotunk úgy, hogy hol legyen az elem stabilizátora . Más szavakkal, az elemek egy alcsoportja, amely az egyes elemeket önmagába fordítja [7] . Ezzel a megközelítéssel minden következő lépésben a halmaz azon része , amelyre a következő alcsoport nem triviálisan hat , egy elemmel csökken, és annak az alcsoportnak a sorrendje, amellyel a munkát végezzük, legalább kétszerese lesz. . Ebből következik, hogy a kívánt partíció megtalálása előtt az algoritmus iterációira lesz szükség [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|)$

A kosettek megszerkesztéséhez ki kell használni azt a tényt, hogy a pálya elemei és a stabilizátor bal oldali kosettjei között egy-egy megfelelés (bijekció) van [19] . $G\omega$ ${\textstyle G/G_{\omega }}$ ${\textstyle G_{\omega ))$

Bizonyíték

A pályákra és stabilizátorokra vonatkozó tétel szerint a kosettek halmaza és a pálya ekvivalens teljesítményű. Minden elemet társítson a pálya egy eleméhez . ${\displaystyle G/G_{\omega ))$ $G\omega$ $t\in G/G_{\omega }$ $t\omega$

Legyen , majd a halmazok és egybeesnek. De ebből az is következik, hogy egybeesik és : $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 egy ω = t egy ( G ω ω ) = ( t egy 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

Minden kosetthez pontosan egy elemet rendeltek hozzá a pályának. Mivel a kosetek az egész csoportot lefedik , minden illeszkedő elem eltérő. Tehát ez valóban egy bijekció. ■ $G$

A bizonyításból következik, hogy a kosetek képviselőiként vehetünk olyan elemeket, amelyek a pálya különböző pontjait valósítják meg [19] . $G\omega$

Tulajdonjogi ellenőrzés

Jelölje olyan elemmel , hogy . A stabilizátorok sorozatára való felosztás lehetővé teszi, hogy ellenőrizze, hogy az elem a [7] csoportba tartozik-e : $\overline u$ ${\displaystyle G/G_{\omega ))$ ${\overline {u}}\omega =u$

Ha , akkor van olyan elem , hogy , azaz , ${\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)))$
A szomszédos osztály elemei és a pálya pontjai közötti bijekció alapján egyértelműen megállapítható, hogy . $t_{i}={\overline {g(\omega _{i})}}$

Ezek a tulajdonságok lehetővé teszik az átmenetet a -ról a -ra , ami végül ahhoz a tényhez vezet, hogy az aktuális elemnek a -ban kell lennie . Ha ez valóban így van, akkor , ahonnan lehetséges a [7] kifejezés . ${\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))$

Pályaszámítás

Legyen a csoportnak generátorkészlete . Bármely elem pályája egy csoport működése alatt a következő formájú fába szervezhető [17] : $G$ $S$ $\alpha$ $G=\langle S\rangle$

Egy elem a fa gyökerére van írva , $\alpha \in \Omega$
A fa minden csúcsára egy elemet írunk az elem pályájáról , ${\textstyle \beta \in G(\alpha )}$ $\alpha$
Az elemet tartalmazó csúcstól az elemet tartalmazó csúcs felé vezető élen van egy olyan elem , hogy . $u$ $v$ $s\in S$ $s(u)=v$

A leírt fa mélységi bejárással is felépíthető , ehhez minden csúcson végig kell rendezni az elemet , amíg ki nem derül, hogy a [17] számára még nincs csúcs kijelölve . Megvalósítási példa Pythonban : $u$ $s\in S$ $s(u)$

# Egy pályafát épít adott w elemnek és S generáló halmaznak build_schreier_tree ( w , S , orbit ): for g in S : if g [ w ] not in orbit : orbit [ g [ w ]] = alkalmaz ( g , orbit [ w ]) build_schreier_tree ( g [ w ], S , orbit )

Itt a függvény visszaadja a csoportművelet elemre történő alkalmazásának eredményét, valamint első és második argumentumként, és az elemet a -ban tárolja . ${\mathsf {apply}}(a,b)$ $a$ $b$ ${\mathsf {orbit}}[\alpha ]$ $\overline {\alpha }$

Schreier lemmája

A Schreier-lemmából az következik, hogy a stabilizátort a Schreier-generátorok halmaza állítja elő: . Ez az eredmény lehetővé teszi, hogy generáló halmazt alkossunk a for generátorkészletből és az elem pályájából . Egy új generátorkészletet visszaadó függvény lehetséges megvalósítása [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 )))$

# Egy generátorkészletet vesz fel G_{w-1}-hez és egy w pályát # Egy generátorkészletet ad vissza G_w def make_gen ( S , orbit ): n = len ( next ( iter ( S ))) newS = set () for s in S : for u in orbit : newS . add ( redukál ( alkalmaz , [ inverz ( kering [ s [ u ]]), s , kering [ u ]])) return newS

Az algoritmus ezzel nem merül ki, hiszen bár az új generátorkészlet mérete polinomiálisan függ a pálya és a régi generátorkészlet méretétől egy egyedi hívás esetén, összességében ennek a függvénynek a hívása esetén a generáló halmaz mérete. halmaz exponenciálisan nő [2] .

Szitáló generátorok

A generátorkészletek ellenőrizetlen növekedésének elkerülése érdekében szitálási eljárást kell alkalmazni . Ehhez a következő nyilatkozatra lenne szükség [3] [20] :

Hadd . Ekkor legfeljebb olyan elemekből álló halmazt lehet megszerkeszteni , hogy . $S\ részhalmaz G$ $S'$ $\vert \Omega \vert ^{2}$ $\langle S'\rangle =\langle S\rangle$

Bizonyíték

Először is bizonyítsuk be a következő lemmát:

Hadd . Ekkor a következő átalakítások nem változnak : $S\ részhalmaz G$ $\langle S\rangle$

Csere számára $s\in S$ $s^{{-1}}$
Csere a következővel: , hol és $s\in S$ $st$ $t\in S$ $t\neq s$

Bizonyíték

E műveletek egyikének alkalmazása után egy halmazt kapunk . Nyilvánvaló, hogy . Másrészt ezek a konverziók megfordíthatók azonos típusú konverziókkal, tehát . Szóval . ■ $S'$ $S'\subset \langle S\rangle$ $S\subset \langle S'\rangle$ $\langle S\rangle =\langle S'\rangle$

Ilyen transzformációk segítségével a halmazt olyan alakra redukálhatjuk, hogy a halmaz bármely párjához legfeljebb egy olyan elem legyen , hogy: $S$ $(i,j)$ $s$

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

Ezt úgy érhetjük el, hogy egyenként hozzáadjuk az elemeket az új halmazhoz , és a Gauss-módszerhez hasonlóan járunk el :

S'

Tegyük fel, hogy egy új elemet szeretnénk hozzáadni , $S'$ $s$
Menjünk egymás után ${\displaystyle \omega _{1},\dots ,\omega _{n))$
1. Ha , akkor menj ide , ${\displaystyle s(\omega _{i})=\omega _{i))$ $\omega _{i+1}$
2. Ha , akkor ellenőrizze, hogy találkozott-e már ilyen párral rendelkező elem , ${\displaystyle s(\omega _{i})=\omega _{j))$ $t$ $(i,j)$
  1. Ha találkoztunk, cserélje ki a következőre, és menjen ide : $s$ $s^{-1}t$ $\omega _{i+1}$
  2. Ellenkező esetben emlékezzen arra, hogy mi felel meg a párnak , és adja hozzá az aktuális formában ehhez : $s$ $(i,j)$ $s$ $S'$
Ha az algoritmus végére megvan , akkor figyelmen kívül hagyjuk és nem változtatunk . $s=e$ $s$ $S'$

Ez az algoritmus csak a fent jelzett elemi műveleteket használja, ezért . Figyeljük meg, hogy ha , akkor , tehát az algoritmusban az átmenet helyes, és minden pár valójában legfeljebb egy permutációnak felel meg. Figyelembe véve, hogy legfeljebb ilyen párok vannak , megkapjuk a szükséges állítást.

■

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

A bizonyításban leírt eljárást Sims-szűrőnek nevezik, és a [21] -ben működik . A megvalósítása így nézhet ki: $O(|S|\cdot \Omega ^{2})$

# Felvesz egy szülőhalmazt S # Egy vékonyított szülőhalmazt ad vissza S' def normalize ( S ): n = len ( next ( iter ( S ))) newS = set () base = [{} for i in range ( n )] s - hez S -ben : x - hez a tartományban ( 0 , n ): ha s [ x ] != x : ha s [ x ] alapban [ x ]: s = alkalmazza ( inverz ( s ) , alap [ x ] [ s ] [ x ]]) else : alap [ x ][ s [ x ]] = s newS . add ( s ) break return newS

A Sims szűrőn kívül a Jerrum szűrővel [22] lehet keresni egy kis készletet . A Sims szűrővel ellentétben, amely a legtöbb elemből álló halmazt találja meg, a Jerrum szűrő legfeljebb egy elemből álló halmazt talál . Ugyanakkor a Jerrum szűrő működik -re , így a Schreier-Sims algoritmus esetén célszerű a Sims szűrőt használni [21] . $S'$ $|\Omega |^{2}$ $|\Omega |$ $O(|S|\cdot |\Omega |^{4})$

Algoritmus

A fentiek együttesen egy olyan algoritmust adnak, amely a következőképpen valósítható meg tömören [20] :

# Egy generátorkészletet vesz fel S = s1, ..., sk # Coset transzverzális U1, ..., Uk def schreier_sims ( S ): n = len ( next ( iter ( S ))) ans = [] w = 0 míg S : orbit = {} keringés [ w ] = sor ( tartomány ( n )) build_schreier_tree ( w , S , orbit ) ans += [[ kering [ i ] for i in orbit ]] S = normalizál ( make_gen ( S , orbit )) w += 1 return ans

Lépésről lépésre cselekvéseinek jelentése a következő:

Az elem pályája mélységi kereséssel épül fel, $\omega _{i}$
Minden Schreier generátor a következőre van kiszámítva : ${\displaystyle G^{(i+1)))$
Sok generátort megtizedelnek, hogy elkerüljék exponenciális növekedésüket.

A kimeneten az algoritmus egy listát ad vissza, amelynek elemei a cosets transzverzálisai . $G^{(0)}/G^{(1)},G^{(1)}/G^{(2)},\dots ,G^{(k-1)}/G^ {(k)}$

Az algoritmus futási ideje

Összességében az algoritmus nem igényel több iterációt. Minden iteráció a következőkből áll: $|\Omega |$

Egy pályafa felépítése, amely elemi műveleteket végez, $O(|S|\cdot |\Omega |)$
A Schreier-generátorok felépítése, amely elemi műveleteket végez, és generátorokat visszaad, $O(|S|\cdot |\Omega |^{2})$ $|S|\cdot |\Omega |$
A generáló halmaz normalizálása, amely elemi műveleteket végez, ahol az előző lépésben kapott halmaz. $O(|S'|\cdot |\Omega |^{2})$ $S'$

Az érték abban az esetben, ha a halmaz adott , nem változik az algoritmus során, és egyenlő: . A generátorkészlet mérete kezdetben egyenlő , és minden további lépésben nem haladja meg a . Így az algoritmus teljes futási ideje a fenti megvalósításban a következőre becsülhető: [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})$

Az algoritmus variációi

Pszeudo-lineáris változatok

Korábban kimutatták, hogy az algoritmus iterációkat igényel. Általános esetben a csoport mérete nagyságrendileg lehet , és ebben az esetben a Stirling-képlet szerint, ami nyilvánvalóan nagyobb . De bizonyos esetekben a csoport sorrendje kicsi, és ezért jövedelmezőbb egy olyan algoritmus használata, amely a -tól függ , és nem - például ha valamilyen ismert csoportról van szó, amelyet permutációs csoportként adnak meg [12] . $\min(|\Omega |,\log |G|)$ $n!$ $\log |G|\sim n\log n$ $|\Omega |=n$ $\log |G|$ $n$

Cayley tétele szerint bármely véges csoport izomorf valamilyen permutációs csoporttal . Egy ilyen csoport mértéke nagy lehet, de sok csoportnál a sorrendjük olyan, hogy . Például a diédercsoport izomorf a ciklikus eltolódás és reflexió által generált permutációs csoporttal . Vagyis ennek a csoportnak a foka , a sorrend pedig , és . Az ilyen csoportokhoz futásidejű algoritmusok jöhetnek számításba , amelyeket pszeudo-lineárisnak neveznek [12] . $n$ $|G|$ $\log |G|<n$ $D_{n}$ $r=(1~~2~~\pontok~~n)$ $s=(1~~n)(2~~n-1)(3~~n-2)\pontok$ $n$ $2n$ $\log |G|\sim \log n$ $O(nm\log ^{c}|G|)$

Annak érdekében, hogy az algoritmust közelebb hozza a pszeudo-lineárishoz, és csökkentse a futási idejében lévő fokot, Sheresh az algoritmus olyan verzióihoz jutott, amelyek megkövetelik [18] : $n$

$O(n^{2}\log ^{3}|G|+mn^{2}\log |G|)$ idő és memória $O(n^{2}\log |G|+mn)$
$O(n^{3}\log ^{3}|G|+mn^{3}\log |G|)$ idő és memória. $O(n\log ^{2}|G|+mn)$

Valószínűségi változat

Az algoritmus első működő valószínűségi változatát Jeffrey Leon fejlesztette ki 1980-ban [11] . Általában erre gondolnak, amikor a valószínűségi Schreyer-Sims módszerről beszélnek. Ebben a Schreier generátorok ritkításánál ez az eljárás idő előtt megszakadt, ha egymás után 20 generátor bizonyult faktorizáltnak. Sheresh megmutatta, hogy néhány optimalizálással együtt ez az eljárás a következő állítást adja [5] :

Bármely konstanshoz létezik egy Monte Carlo-típusú algoritmus , amely maximum hibavalószínűséggel egy erős generátorkészletet hoz létre a permutációs csoporthoz idő és memória felhasználásával . $d$ ${\displaystyle n^{-d))$ $G=\langle S\rangle$ $O(n\log n\log ^{4}|G|+mn\log |G|)$ $O(n\log |G|+mn)$

A modern számítógépes algebrai rendszerekben általában az algoritmus ezen változatának különféle heurisztikájú módosításait használják a program gyorsítására [5] .

Jegyzetek

↑ 1 2 3 Sims, 1970 , p. 169-170.
↑ 1 2 3 4 5 Murray, 2003 , p. 1-3.
↑ 1 2 3 4 5 Holt, Eyck, O'Brien, 2005 , p. 87-90.
↑ 1 2 Sheresh, 2003 , p. 1-4.
↑ 1 2 3 4 Sheresh, 2003 , p. 62-64.
↑ 1 2 Brouwer, 2016 , p. négy.
↑ 1 2 3 4 5 6 7 Sims, 1970 , p. 176-177.
↑ 1 2 Furst, Hopcroft, Lax, 1980 .
↑ Jerrum, 1986 .
↑ Knuth, 1991 .
↑ 1 2 Leon, 1980 .
↑ 1 2 3 4 Sheresh, 2003 , p. 48-54.
↑ 1 2 Holt, Eyck, O'Brien, 2005 , p. 93-94.
↑ Zhuravlev, Flerov, Vyaly, 2019 , Permutációk, p. 31-36.
↑ Holt, Eyck, O'Brien, 2005 , p. 1-7.
↑ Murray, O'Brien, 1995 .
↑ 1 2 3 Murray, 2003 , p. 9-24.
↑ 1 2 Sheresh, 2003 , p. 59-62.
↑ 1 2 Zhuravlev, Flerov, Vyaly, 2019 , Keringők és stabilizátorok, p. 140-145.
↑ 1 2 3 Murray, 2003 , p. 25-33.
↑ 1 2 Vipul Naik. Sims szűrő (angol) . Groupprops, The Group Properties Wiki . Letöltve: 2019. szeptember 23. Az eredetiből archiválva : 2019. szeptember 1.
↑ Vipul Naik. Jerrum szűrője . Groupprops, The Group Properties Wiki . Letöltve: 2023. szeptember 19. Az eredetiből archiválva : 2019. szeptember 1..

Irodalom

Yu. I. Zhuravlev , Yu. A. Flerov és M. N. Vyaly A magasabb algebra és a kódoláselmélet alapjai . - FUPM MIPT, 2019. - S. 144. - 305 p.
Charles C. Sims. Számítási módszerek a permutációs csoportok tanulmányozásában (angol) // Computational Problems in Abstract Algebra. - Elsevier, 1970. - P. 176-177. — ISBN 9780080129754 .
Derek F. Holt, Bettina Eick, Eamonn A. O'Brien. Handbook of Computational Group Theory (angol) . – New York: Chapman és Hall/CRC, 2005. – 536 p. — ISBN 9780429147944 .
Merrick Furst, John Hopcroft, Eugene Luks. Polynomial-time algoritms for permutation group (angol) // 21st Annual Symposium on Foundations of Computer Science (sfcs, 1980). - IEEE, 1980. - doi : 10.1109/sfcs.1980.34 .
Scott H. Murray. Schreier-Sims algoritmus (angol) // Matematika Tanszék, Australian National University. – 2003.
TC Brouwer. Önkényes permutációs rejtvény megoldása (angol) // Mathematisch Instituut, Universiteit Leiden. — 2016.
Seress Ákos. Permutációs csoport algoritmusok (angol) // Cambridge Core. - 2003. - ISBN 9780511546549 . - doi : 10.1017/CBO9780511546549 .
Mark Jerrum. A permutációs csoportok kompakt ábrázolása (angol) // Journal of Algorithms. - 1986. - 1. évf. 7 , iss. 1 . — P. 60–78. — ISSN 0196-6774 . - doi : 10.1016/0196-6774(86)90038-6 .
Donald E. Knuth. Perm-csoportok hatékony ábrázolása (angol) // Combinatorica. - 1991. - 1. évf. 11 , iss. 1 . — P. 33–43. — ISSN 1439-6912 0209-9683, 1439-6912 . - doi : 10.1007/bf01375471 .
Jeffrey S. Leon Egy algoritmusról egy bázis és egy erős generátorkészlet megtalálására egy permutációk generálásával adott csoporthoz // Számítás matematikája. - 1980. - 1. évf. 35 , iss. 151 . - P. 941-974. — ISSN 0025-5718 . - doi : 10.1090/s0025-5718-1980-0572868-5 .
Scott H. Murray, EA O'Brien. Bázispontok kiválasztása a Schreier-Sims algoritmushoz mátrixcsoportokhoz // Journal of Symbolic Computation. - 1995. - 1. évf. 19 , iss. 6 . - P. 577-584. — ISSN 0747-7171 . - doi : 10.1006/jsco.1995.1033 .

Csoportelmélet
Alapfogalmak	Alcsoport Normál alcsoport Tényezőcsoport Munka közvetlen félig közvetlen ingyenes
Algebrai tulajdonságok	kommutatív csoport Ciklikus csoport rendelt csoport Transform Group Megoldható csoport Schreier Lemmája Lagrange-tétel Sylow tételei Egyszerű véges csoportok osztályozása
véges csoportok	C n véges ciklikus csoport Szimmetrikus csoport S n Diéder csoport D n Váltakozó csoport A n Klein négyes csoport Mathieu csoportok M11_ _ M12_ _ M22 _ M23_ _ M24 _ Conway csoportok Co 1 Co2_ _ Co3_ _ Jankó csoportok J1_ _ J2_ _ J3_ _ J4_ _ Fisher csoportok F22_ _ F 23 F24 _ Szörny (M)
Topológiai csoportok	Hazugságcsoportok O(n) ortogonális csoport Speciális ortogonális csoport SO(n) U(n) egységes csoport Különleges egységes csoport SU(n) Szimlektikus csoport Sp(n) Kivételes Egyszerű Lorentz csoport Poincaré csoport
Algoritmusok csoportokon	Schreier – Sims Todd – Coxeter Fourier transzformáció