Schreier-Sims algoritm | |
---|---|
Earl Cayley Group | |
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 |
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] .
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] .
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] .
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] .
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] :
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] .
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] :
Låt vara en serie av undergrupper . Då kan vilket element som helst representeras unikt som , där . |
Vyn som beskrivs ovan har följande egenskaper:
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] .
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] .
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] .
BevisEnligt satsen om banor och stabilisatorer är uppsättningen av coset och omloppsbana ekvivalenta i kraft. Associera varje element med ett element i omloppsbanan .
Låt , då uppsättningarna och sammanfalla. Men av detta följer att också sammanfaller och :
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 }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. ■
Det följer av beviset att man som representanter för coset kan ta element som realiserar olika punkter i omloppsbanan [19] .
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] :
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] .
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] :
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 :
# 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 .
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] :
# 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 newSAlgoritmen ä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] .
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 . |
Låt oss först bevisa följande lemma:
Låt . Då ändras inte följande transformationer :
|
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å . ■
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 ( ω 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}} 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 :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.
■Proceduren som beskrivs i beviset kallas Sims-filtret och fungerar i [21] . Dess implementering kan se ut så här:
# 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 nySFö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] .
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 ansSteg för steg har dess handlingar följande betydelse:
Vid utgången kommer algoritmen att returnera en lista vars element är transversaler av coset .
Totalt kräver algoritmen inga fler iterationer. Varje iteration består av:
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] .
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] .
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] .
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] :
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. |
I moderna datoralgebrasystem används vanligtvis modifieringar av denna version av algoritmen med olika heuristik för att påskynda programmet [5] .
Gruppteori | |
---|---|
Grundläggande koncept | |
Algebraiska egenskaper | |
ändliga grupper |
|
Topologiska grupper | |
Algoritmer på grupper |