Algoritmus Steinhaus – Johnson – Trotter - Steinhaus–Johnson–Trotter algorithm

The Hamiltonovský cyklus v Cayleyův graf symetrické skupiny generované algoritmem Steinhaus – Johnson – Trotter

Obměny čtyř prvků, založené na prvcích inverze sady (sady dvojic prvků mimo jejich přirozený řád), inverzní vektory a čísla inverze

Inverzní sady tvoří šedý kód, tedy také inverzní vektory (součty vzestupných úhlopříček trojúhelníků) a inverzní čísla.

Čísla nalevo jsou obrácením permutací colexicographic indexy (porovnej seznam v přirozeném pořadí ) a tvoří řádek 4 trojúhelníku OEIS: A280319

Inverzní sady permutací 12 míst od sebe jsou doplňuje.

Schéma kola všech permutací délky ${ displaystyle n = 4}$ generováno algoritmem Steinhaus-Johnson-Trotter, kde je každá permutace barevně odlišena (1 = modrá, 2 = zelená, 3 = žlutá, 4 = červená).

The Algoritmus Steinhaus – Johnson – Trotter nebo Algoritmus Johnson-Trotter, také zvaný prosté změny, je algoritmus pojmenoval podle Hugo Steinhaus, Selmer M. Johnson a Hale F. Trotter který generuje všechny obměny z n elementy. Každá permutace v sekvenci, kterou generuje, se liší od předchozí permutace záměnou dvou sousedních prvků sekvence. Ekvivalentně tento algoritmus najde a Hamiltonovský cyklus v permutohedron.

Tato metoda byla známa již angličtině v 17. století změnit vyzváněcí tóny, a Sedgewick (1977) nazývá to „snad nejvýznamnějším algoritmem výčtu permutací“. Kromě toho, že je jednoduchý a výpočetně efektivní, má tu výhodu, že mohou být urychleny následné výpočty permutací, které generuje, protože tyto permutace jsou si navzájem velmi podobné.^[1]

Rekurzivní struktura

Pořadí permutací pro dané číslo n lze vytvořit ze sledu permutací pro n - 1 umístěním čísla n do každé možné polohy v každé z kratších permutací. Když je permutace zapnutá n - 1 položka je dokonce permutace (jak to platí pro první, třetí atd., permutace v pořadí), pak číslo n je umístěn na všech možných pozicích v sestupném pořadí od n až 1; když je permutace zapnutá n - 1 položka je lichá, číslo n je umístěn na všech možných pozicích ve vzestupném pořadí.^[2]

Z jediné permutace na jednom prvku tedy

1

jeden může umístit číslo 2 na každou možnou pozici v sestupném pořadí a vytvořit seznam dvou permutací na dvou prvcích,

1 2

2 1

Potom lze umístit číslo 3 do každé ze tří různých pozic pro tyto dvě permutace, v sestupném pořadí pro první permutaci 1 2 a poté ve vzestupném pořadí pro permutaci 2 1:

1 2 3

1 3 2

3 1 2

3 2 1

2 3 1

2 1 3

Na další úrovni rekurze by bylo číslo 4 zařazeno v sestupném pořadí do 1 2 3ve vzestupném pořadí do 1 3 2, v sestupném pořadí do 3 1 2Stejný vzor umístění, střídavě mezi sestupným a vzestupným umístěním n, platí pro jakoukoli větší hodnotunTímto způsobem se každá permutace liší od té předchozí buď pohybem jedné polohy v čase n, nebo změnou dvou menších čísel zděděných z předchozí sekvence kratších permutací. V obou případech je tento rozdíl pouze transpozicí dvou sousedních prvků. Když n > 1 první a poslední prvek sekvence se také liší pouze ve dvou sousedních prvcích (pozice čísel 1 a 2), jak je možné ukázat indukcí.

Ačkoli tuto sekvenci může generovat a rekurzivní algoritmus který vytvoří sekvenci menších permutací a poté provede všechny možné vložení největšího počtu do rekurzivně generované sekvence, skutečný algoritmus Steinhaus-Johnson-Trotter se vyhne rekurzi a místo toho vypočítá stejnou sekvenci permutací iterativní metodou.

Existuje ekvivalentní a koncepčně poněkud jednodušší definice Steinhaus-Johnson-Trotterova uspořádání permutací pomocí následujícího chamtivého algoritmu^[3]: Začínáme s permutací identity ${ displaystyle 1 ; 2 ; ldots ; n}$Nyní nyní opakovaně transponujeme největší možný záznam se záznamem nalevo nebo napravo, takže v každém kroku se vytvoří nová permutace, se kterou se v seznamu permutací dosud nesetkala.Například v případě ${ displaystyle n = 3}$ začneme s 123, pak otočíme 3 s jeho levým sousedem a dostaneme 132. Potom otočíme 3 s jeho levým sousedem 1, protože převrácení 3 s jeho pravým sousedem 2 by přineslo znovu 123, což jsme již viděli, takže dorazíme na 312 atd. Směr transpozice (vlevo nebo vpravo) je v tomto algoritmu vždy jednoznačně určen.

Algoritmus

Jak popisuje Johnson (1963), algoritmus pro generování další permutace z dané permutace π provede následující kroky

• Pro každého i od 1 do n, nechť X_i být pozice, kde je hodnota i je umístěn v permutaci π. Pokud je pořadí čísel od 1 do i - 1 v permutaci π definuje dokonce permutace, nechť y_i = X_i - 1; jinak nechte y_i = X_i + 1.
• Najděte největší číslo i pro který y_i definuje platnou pozici v permutaci π, která obsahuje číslo menší neži. Zaměňte hodnoty v pozicích X_i a y_i.

Když žádné čísloi lze nalézt splnění podmínek druhého kroku algoritmu, algoritmus dosáhl konečné permutace sekvence a končí. Tento postup může být implementován v O (n) čas na obměnu.

Trotter (1962) dává alternativní implementaci iteračního algoritmu pro stejnou sekvenci, lehce komentováno ALGOL 60 notace.

Protože tato metoda generuje permutace, které se střídají mezi sudými a lichými, lze ji snadno upravit tak, aby generovala pouze sudé permutace nebo pouze liché permutace: ke generování další permutace stejné parity z dané permutace jednoduše použijte stejný postup dvakrát .^[4]

Dokonce i zrychlení

Následné vylepšení o Shimon Even poskytuje vylepšení doby chodu algoritmu uložením dalších informací o každém prvku v permutaci: jeho pozici a směr (kladné, záporné nebo nulové), ve kterém se aktuálně pohybuje (v zásadě se jedná o stejnou informaci vypočítanou pomocí parity permutace v Johnsonově verzi algoritmu). Zpočátku je směr čísla 1 nulový a všechny ostatní prvky mají záporný směr:

1 −2 −3

V každém kroku algoritmus najde největší prvek s nenulovým směrem a zamění jej v naznačeném směru:

1 −3 −2

Pokud to způsobí, že vybraný prvek dosáhne první nebo poslední polohy v rámci permutace, nebo pokud je další prvek ve stejném směru větší než vybraný prvek, je směr vybraného prvku nastaven na nulu:

3 1 −2

Po každém kroku mají všechny prvky větší než vybraný prvek (který měl dříve směr nula) nastaveny směry, které indikují pohyb směrem k vybranému prvku. To znamená pozitivní pro všechny prvky mezi začátkem permutace a vybraným prvkem a negativní pro prvky ke konci. V tomto příkladu tedy po pohybu čísla 2 bude číslo 3 znovu označeno směrem:

+3 2 1

Zbývající dva kroky algoritmu pro n = 3 jsou:

2 +3 1

2 1 3

Když všechna čísla přestanou být označena, algoritmus se ukončí.

Tento algoritmus vyžaduje čas O (i) pro každý krok, ve kterém je největší počet k pohybu n − i + 1. Tedy swapy zahrnující číslo n trvat jen konstantní čas; protože tyto swapy představují všechny kromě 1 /n zlomek všech swapů prováděných algoritmem, průměrná doba na generovanou permutaci je také konstantní, i když malý počet permutací bude trvat déle.^[1]

Složitější bezmocný verze stejného postupu umožňuje jeho provedení v každém případě v konstantní době na permutaci; Úpravy potřebné k vyloučení smyček z postupu jej však v praxi zpomalují.^[5]

Geometrická interpretace

Sada všech permutací n položky mohou být geometricky reprezentovány a permutohedron, polytop vytvořený z konvexní obal z n! vektory, permutace vektoru (1,2, ...n). Ačkoli je takto definováno v n-dimenzionální prostor, je to vlastně (n - 1) -rozměrný mnohostěn; například permutohedron na čtyřech položkách je trojrozměrný mnohostěn, zkrácený osmistěn. Pokud je každý vrchol permutohedronu označen pomocí inverzní permutace k permutaci definované jeho souřadnicemi vrcholů, výsledné označení popisuje a Cayleyův graf z symetrická skupina permutací na n položky generované permutacemi, které zaměňují sousední páry položek. Každé dvě po sobě jdoucí permutace v sekvenci generované algoritmem Steinhaus-Johnson-Trotter tedy odpovídají dvěma vrcholům, které tvoří koncové body hrany v permutohedronu, a celá posloupnost permutací popisuje Hamiltonova cesta v permutohedronu, cesta, která prochází každým vrcholem přesně jednou. Pokud je sekvence permutací dokončena přidáním jedné další hrany z poslední permutace k první v sekvenci, výsledkem je místo toho hamiltonovský cyklus.^[6]

Vztah k šedým kódům

A Šedý kód pro čísla v daném základ je posloupnost, která obsahuje každé číslo až do daného limitu přesně jednou, a to takovým způsobem, že každá dvojice po sobě jdoucích čísel se liší o jedno v jedné číslici. The n! obměny n čísla od 1 do n mohou být umístěny v individuální korespondenci s n! čísla od 0 do n! - 1 spárováním každé permutace se sekvencí čísel C_i které počítají počet pozic v permutaci, které jsou napravo od hodnoty i a které obsahují hodnotu menší neži (tj. počet inverze pro který i je větší ze dvou obrácených hodnot) a poté tyto sekvence interpretuje jako čísla v systém faktoriálových čísel, toto je smíšený radix systém s radixovou sekvencí (1,2,3,4, ...). Například permutace (3,1,4,5,2) by dala hodnoty C₁ = 0, C₂ = 0, C₃ = 2, C₄ = 1 a C₅ = 1. Pořadí těchto hodnot (0,0,2,1,1) dává číslo

0 × 0! + 0 × 1! + 2 × 2! + 1 × 3! + 1 × 4! = 34.

Po sobě jdoucí permutace v sekvenci generované algoritmem Steinhaus – Johnson – Trotter mají počty inverzí, které se liší o jednu, tvoří šedý kód pro systém faktoriálových čísel.^[7]

Obecněji řečeno, kombinatorické algoritmy vědci definovali šedý kód pro sadu kombinatorických objektů jako uspořádání pro objekty, ve kterých se každý dva po sobě jdoucí objekty liší minimálním možným způsobem. V tomto obecném smyslu generuje algoritmus Steinhaus-Johnson-Trotter Grayův kód pro samotné permutace.

Dějiny

Algoritmus je pojmenován po Hugo Steinhaus, Selmer M. Johnson a Hale F. Trotter. Johnson a Trotter objevili algoritmus nezávisle na sobě na počátku 60. let. Kniha Steinhausa, původně publikovaná v roce 1958 a přeložená do angličtiny v roce 1963, popisuje související hádanku generování všech permutací systémem částic, z nichž každá se pohybuje konstantní rychlostí podél čáry a vyměňuje polohy, když jedna částice předběhne druhou. Žádné řešení není možné n > 3, protože počet swapů je mnohem menší než počet permutací, ale algoritmus Steinhaus – Johnson – Trotter popisuje pohyb částic s nekonstantní rychlostí, které generují všechny permutace.

Mimo matematiku byla stejná metoda známá mnohem déle jako metoda pro změnit vyzvánění kostelních zvonů: udává postup, kterým lze zvonit sadu zvonů všemi možnými permutacemi, přičemž se mění pořadí pouze dvou zvonů na změnu. Tyto takzvané „prosté změny“ byly zaznamenány již v roce 1621 pro čtyři zvony a knihu z roku 1677 Fabian Stedman uvádí seznam řešení až pro šest zvonů. V poslední době se změna vyzvánění řídila pravidlem, že žádný zvon nesmí zůstat ve stejné poloze po tři po sobě jdoucí obměny; toto pravidlo je prostými změnami porušeno, takže byly navrženy další strategie, které vyměňují více zvonů za změnu.^[8]

Viz také

• Haldy algoritmus
• Fisher – Yates zamíchá

Poznámky

Reference