Steinhaus–Johnson–Trotter-algoritm

Hamiltoncykeln i Cayley-grafen för den symmetriska gruppen som genereras av Steinhaus-Johnson-Trotter- algoritmen

Permutationerna av fyra element, deras elementbaserade inversionsmängder (uppsättningar av elementpar utanför deras naturliga ordning), inversionsvektorer och inversionstal. Inversionsmängderna bildar en grå kod, alltså även inversionsvektorerna (summor av trianglarnas stigande diagonaler) och inversionstal. Siffrorna till vänster är permutationernas omvända kolexikografiska index (jämför lista i naturlig ordning ) och bildar rad 4 i triangeln OEIS : A280319 Inversionsuppsättningarna av permutationer 12 platser från varandra är komplement .

Hjuldiagram över alla permutationer med längden $n=4$ genererat av Steinhaus-Johnson-Trotter-algoritmen, där varje permutation är färgkodad (1=blå, 2=grön, 3=gul, 4=röd ).

Steinhaus –Johnson–Trotter-algoritmen eller Johnson–Trotter-algoritmen , även kallad plain changes , är en algoritm uppkallad efter Hugo Steinhaus , Selmer M. Johnson och Hale F. Trotter som genererar alla permutationer av $n$ -element. Varje permutation i sekvensen som den genererar skiljer sig från den tidigare permutationen genom att byta två intilliggande element i sekvensen. På motsvarande sätt hittar denna algoritm en Hamiltonsk cykel i permutoedern .

Denna metod var känd redan för 1600-talets engelska växlingsringare , och Sedgewick (1977) kallar den "kanske den mest framträdande permutationsuppräkningsalgoritmen". En version av algoritmen kan implementeras på ett sådant sätt att den genomsnittliga tiden per permutation är konstant. Förutom att den är enkel och beräkningseffektiv har denna algoritm fördelen att efterföljande beräkningar av de permutationer som den genererar kan påskyndas på grund av likheten mellan konsekutiva permutationer som den genererar.

Algoritm

Sekvensen av permutationer som genereras av Steinhaus-Johnson-Trotter-algoritmen har en naturlig rekursiv struktur, som kan genereras av en rekursiv algoritm. Men den faktiska Steinhaus-Johnson-Trotter-algoritmen använder inte rekursion, utan beräknar istället samma sekvens av permutationer med en enkel iterativ metod. En senare förbättring gör att den kan köras med konstant genomsnittlig tid per permutation.

Rekursiv struktur

Sekvensen av permutationer för ett givet tal $n$ kan bildas från sekvensen av permutationer för $n-1$ genom att placera talet $n$ i varje möjlig position i var och en av de kortare permutationerna. Steinhaus–Johnson–Trotter-algoritmen följer denna struktur: sekvensen av permutationer som den genererar består av $(n-1)!$ block av permutationer, så att permutationerna inom varje block överensstämmer med ordningen på talen från 1 till $n-1$ och skiljer sig endast i positionen för ${ \displaystyle n}$ . Själva blocken är ordnade rekursivt, enligt Steinhaus–Johnson–Trotter-algoritmen för ett element mindre. Inom varje block förekommer positionerna där $n$ placeras antingen i fallande eller stigande ordning, och blocken växlar mellan dessa två ordningsföljder: placeringarna av $n$ i det första blocket är i fallande ordning , i det andra blocket är de i stigande ordning, i det tredje blocket är de i fallande ordning, och så vidare.

Alltså, från den enda permutationen på ett element,

1

man kan placera siffran 2 i varje möjlig position i fallande ordning för att bilda en lista med två permutationer på två element,

1 2

2 1

Sedan kan man placera siffran 3 i var och en av tre olika positioner för dessa två permutationer, i fallande ordning för den första permutationen 1 2 och sedan i stigande ordning för permutationen 2 1:

1 2 3

1 3 2

3 1 2

3 2 1

2 3 1

2 1 3

Samma placeringsmönster, alternerande mellan fallande och stigande placeringar av $n$ , gäller för alla större värden på $n$ . I sekvenser av permutationer med denna rekursiva struktur skiljer sig varje permutation från den föregående antingen genom rörelsen med en enda position i taget av ${\displaystyle n} ,$ eller genom en förändring av två mindre tal som ärvts från den föregående sekvensen av kortare permutationer. I båda fallen är denna skillnad bara transponeringen av två intilliggande element. När $n>1$ skiljer sig de första och sista elementen i sekvensen också i endast två intilliggande element (positionerna för talen $1$ och ${\displaystyle 2} )$ , som kan bevisas genom induktion.

Denna sekvens kan genereras av en rekursiv algoritm som konstruerar sekvensen av mindre permutationer och sedan utför alla möjliga infogningar av det största antalet i den rekursivt genererade sekvensen. Samma ordning av permutationer kan också beskrivas på samma sätt som den ordning som genereras av följande giriga algoritm. Börja med identitetspermutationen $1\;2\;\ldots \;n$ . Transponera nu den största möjliga posten upprepade gånger med posten till vänster eller höger, så att i varje steg skapas en ny permutation som inte har påträffats i listan över permutationer tidigare. Till exempel, i fallet $n=3$ börjar sekvensen med $1\;2\;3$ och vänder sedan $3$ med sin vänstra granne för att få $1\;3\;2$ . Från denna punkt skulle vändning av $3$ med dess högra granne $2$ ge den initiala permutationen $1\;2\;3$ , så sekvensen vänder istället $3$ med sin vänstra granne $1$ och kommer fram till $3\;1\;2$ etc. Transpositionens riktning (vänster eller höger) bestäms alltid unikt i denna algoritm. Den faktiska Steinhaus–Johnson–Trotter-algoritmen använder dock inte rekursion och behöver inte hålla reda på de permutationer som den redan har stött på. Istället beräknar den samma sekvens av permutationer med en enkel iterativ metod .

Original version

Som beskrivs av Johnson (1963) , utför algoritmen för att generera nästa permutation från en given permutation $\pi$ följande steg.

• För varje $i$ från 1 till $n$ , låt $x_{i}$ vara den position där värdet $i$ placeras i permutation $\ pi$ . Om ordningen på talen från 1 till $i-1$ i permutation $\pi$ definierar en jämn permutation , låt $y_{i}=x_ {i}-1$ annars, låt $y_{i}=x_{i}+1$ .
• Hitta det största talet $i$ för vilket $y_{i}$ definierar en giltig position i permutationen $\pi$ som innehåller ett tal mindre än $i$ . Byt värdena i positionerna $x_{i}$ och $y_{i}$ .

När inget nummer $i$ kan hittas som uppfyller villkoren för det andra steget i algoritmen, har algoritmen nått den slutliga permutationen av sekvensen och avslutas. Denna procedur kan implementeras i $O(n)$ tid per permutation.

Trotter (1962) ger en alternativ implementering av en iterativ algoritm för samma sekvens, i lätt kommenterad ALGOL 60- notation.

Eftersom denna metod genererar permutationer som växlar mellan att vara jämna och udda, kan den lätt modifieras för att generera endast de jämna permutationerna eller endast de udda permutationerna: för att generera nästa permutation av samma paritet från en given permutation, använd helt enkelt samma procedur två gånger .

Evens snabbare

En efterföljande förbättring av Shimon Even ger en förbättring av körtiden för algoritmen genom att lagra ytterligare information för varje element i permutationen: dess position och en riktning (positiv, negativ eller noll) i vilken den för närvarande rör sig (i huvudsak, detta är samma information som beräknas med hjälp av pariteten för permutationen i Johnsons version av algoritmen). Inledningsvis är riktningen för talet 1 noll, och alla andra element har en negativ riktning:

1 −2 −3

Vid varje steg hittar algoritmen det största elementet med en riktning som inte är noll och byter det i den angivna riktningen:

1 −3 −2

Om detta gör att det valda elementet når den första eller sista positionen inom permutationen, eller om nästa element i samma riktning är större än det valda elementet, sätts riktningen för det valda elementet till noll:

3 1 −2

Efter varje steg har alla element större än det valda elementet (som tidigare hade riktning noll) sina riktningar inställda för att indikera rörelse mot det valda elementet. Det vill säga positivt för alla element mellan början av permutationen och det valda elementet, och negativt för element mot slutet. I det här exemplet, efter att siffran 2 har flyttats, markeras siffran 3 med en riktning igen:

+3 2 1

De återstående två stegen i algoritmen för $n=3$ är:

2 +3 1

2 1 3

När alla siffror blir omarkerade avslutas algoritmen.

Denna algoritm tar tid $O(i)$ för varje steg där det största antalet att flytta är $n-i+1$ . Således tar byten som involverar talet $n$ endast konstant tid; eftersom dessa swappar står för alla utom en $1/n$ bråkdel av alla swappar som utförs av algoritmen, är den genomsnittliga tiden per genererad permutation också konstant, även om ett litet antal permutationer tar ett större tid.

En mer komplex slinglös version av samma procedur gör att den kan utföras i konstant tid per permutation i varje fall; Men modifieringarna som behövs för att eliminera slingor från proceduren gör det långsammare i praktiken.

Relaterade strukturer

Permutoeder

Uppsättningen av alla permutationer av $\displaystyle n}$ { objekt kan representeras geometriskt av en permutohedron , polytopen bildad av det konvexa skrovet av $n!$ vektorer, permutationerna av vektorn $(1,2,\dots n)$ . Även om det definieras på detta sätt i $n$ -dimensionellt utrymme, är det faktiskt en $(n-1)$ -dimensionell polytop; till exempel är permutoedern på fyra objekt en tredimensionell polyeder, den trunkerade oktaedern . Om varje vertex i permutoedern är märkt av den inversa permutationen till permutationen som definieras av dess vertexkoordinater, beskriver den resulterande märkningen en Cayley-graf av den symmetriska gruppen av permutationer på $n$ objekt, som genereras av permutationerna som växlar intilliggande par av föremål. Således motsvarar varje två på varandra följande permutationer i sekvensen som genereras av Steinhaus-Johnson-Trotter-algoritmen på detta sätt två hörn som bildar ändpunkterna för en kant i permutoedern, och hela sekvensen av permutationer beskriver en Hamiltonsk väg i permutoederen , en bana som passerar genom varje vertex exakt en gång. Om sekvensen av permutationer fullbordas genom att lägga till ytterligare en kant från den sista permutationen till den första i sekvensen, blir resultatet istället en Hamiltonsk cykel.

Grå koder

En grå kod för tal i en given radix är en sekvens som innehåller varje nummer upp till en given gräns exakt en gång, på ett sådant sätt att varje par av på varandra följande tal skiljer sig med ett i en enda siffra. Den $n!$ permutationer av de $n$ talen från 1 till $n$ kan placeras i en-till-en-korrespondens med $n!$ nummer från 0 till $n!-1$ genom att para ihop varje permutation med nummersekvensen $c_{i}$ som räknar antalet positioner i permutationen som är till höger om värdet $i$ och som innehåller ett värde mindre än $i$ (det vill säga antalet inversioner för vilka $i$ är det största av de två inverterade värdena), och sedan tolka dessa sekvenser som tal i faktorialen talsystem , det vill säga det blandade radixsystemet med radixsekvens $(1,2,3,4,\dots )$ Till exempel permutationen $(3,1,4,5,2)$ skulle ge värdena $c_{1}=0$ , $c_{2}= 0$ , $c_{3}=2$ , $c_{4}=1$ och $c_{5}=1$ . Sekvensen av dessa värden, $(0,0,2,1,1)$ , ger talet

$$0\ gånger 0!+0\ gånger 1!+2\ gånger 2!+1\ gånger 3!+1\ gånger 4!=34.$$

Konsekutiva permutationer i sekvensen som genereras av Steinhaus–Johnson–Trotter-algoritmen har antal inversioner som skiljer sig åt med en, och bildar en grå kod för det faktoriella talsystemet.

Mer generellt har forskare av kombinatoriska algoritmer definierat en grå kod för en uppsättning kombinatoriska objekt för att vara en ordning för de objekt där varje två på varandra följande objekt skiljer sig åt på ett minimalt sätt. I denna generaliserade mening genererar Steinhaus–Johnson–Trotter-algoritmen en Gray-kod för själva permutationerna.

Historia

Metoden var känd under en stor del av historien som en metod för att ändra ringning av kyrkklockor: den ger en procedur genom vilken en uppsättning klockor kan ringas genom alla möjliga permutationer, vilket ändrar ordningen på endast två klockor per byte. Dessa så kallade "släta förändringar" registrerades så tidigt som 1621 för fyra klockor, och en bok från 1677 av Fabian Stedman listar lösningarna för upp till sex klockor. På senare tid har byte av ringsignaler följt en regel att ingen klocka får stanna i samma position under tre på varandra följande permutationer; denna regel bryts av de vanliga ändringarna, så andra strategier som byter flera klockor per förändring har utarbetats.

Algoritmen är uppkallad efter Hugo Steinhaus , Selmer M. Johnson och Hale F. Trotter . Johnson och Trotter återupptäckte algoritmen oberoende av varandra i början av 1960-talet. En bok av Steinhaus, ursprungligen publicerad 1958 och översatt till engelska 1963, beskriver ett relaterat pussel med att generera alla permutationer av ett system av partiklar, som var och en rör sig med konstant hastighet längs en linje och byter positioner när en partikel kör om en annan. Ingen lösning är möjlig för $n>3$ eftersom antalet byten är mycket färre än antalet permutationer, men Steinhaus–Johnson–Trotter-algoritmen beskriver rörelsen hos partiklar med icke-konstanta hastigheter som genererar alla permutationer.

Se även

• Heaps algoritm , en annan metod för att lista alla permutationer
• Fisher–Yates shuffle , en metod för att generera slumpmässiga permutationer

Anteckningar

•    Dershowitz, Nachum (1975), "En förenklad loop-fri algoritm för att generera permutationer", Nordisk Tidskr. Informationsbehandling (BIT) , 15 (2): 158–164, doi : 10.1007/bf01932689 , MR 0502206 , S2CID 121353303
•    Dijkstra, Edsger W. (1976), "On a gauntlet thrown by David Gries" (PDF) , Acta Informatica , 6 (4): 357–359, doi : 10.1007/BF00268136 , MR 0426492 70 , S85800 5 . Även om Dijkstra inte citerar någon tidigare litteratur, avslöjar ett tidigare utkast till EWD502 att han kände till Trotter (1962) .
•   Ehrlich, Gideon (1973), "Slinglösa algoritmer för att generera permutationer, kombinationer och andra kombinatoriska konfigurationer", Journal of the ACM , 20 (3): 500–513, doi : 10.1145 /321765.321781 , S2CID 6333
• Even, Shimon (1973), Algorithmic Combinatorics , Macmillan
•    Johnson, Selmer M. (1963), "Generation of permutations by adjacent transposition", Mathematics of Computation , 17 (83): 282–285, doi : 10.1090/S0025-5718-1963-0159764-2 , JSTOR 4064-2 , JSTOR 460000
• Lenstra, JK ; Rinnooy Kan, AHG (september 1979), "A rekursive approach to the implementation of enumerative methods", Proceedings of the School on Analysis and Design of Algorithms in Combinatorial Optimization, Udine, Italien (PDF) , Teknisk rapport 8003/0, Erasmus University Rotterdam ; se avsnitt 2.1, "En minimiförändringsgenerator", s. 3–8
• Knuth, Donald (2011), "Avsnitt 7.2.1.2: Generera alla permutationer" , The Art of Computer Programming, volym 4A: Combinatorial Algorithms, Del 1
•   McGuire, Gary (2003), Bells, motell and permutation groups , CiteSeerX 10.1.1.6.5544
•     Savage, Carla (1997), "A survey of combinatorial Grey codes", SIAM Review , 39 (4): 605–629, Bibcode : 1997SIAMR..39..605S , CiteSeerX 10.1.1.39.1924 , doi .401S 2 , JSTOR 2132693 , MR 1491049
•   Sedgewick, Robert (1977), "Permutation generation methods", ACM Comput. Surv. , 9 (2): 137–164, doi : 10.1145/356689.356692 , S2CID 12139332
•   Steinhaus, Hugo (1964), Hundra problem i elementär matematik , New York: Basic Books, s. 49–50, MR 0157881
•   Trotter, HF (augusti 1962), "Algorithm 115: Perm", Communications of the ACM , 5 (8): 434–435, doi : 10.1145/368637.368660 , S2CID 1013826
• Williams, Aaron (2013), "The Greedy Grey Code Algorithm", i Dehne, Frank; Solis-Oba, Roberto; Sack, Jörg-Rüdiger (red.), Algorithms and Data Structures - 13th International Symposium, WADS 2013, London, ON, Kanada, 12-14 augusti 2013. Proceedings , Lecture Notes in Computer Science, vol. 8037, Springer, s. 525–536, doi : 10.1007/978-3-642-40104-6_46