Permutace - Permutation

V matematiky , je permutace ze sady je, volně řečeno, uspořádání svých členů do sekvence nebo lineárním pořadí , nebo v případě, že soubor je již nařízeno, přeskupení jeho prvky. Slovo „permutace“ také označuje akt nebo proces změny lineárního pořadí uspořádané množiny.

Permutace se liší od kombinací , což jsou výběry některých členů množiny bez ohledu na pořadí. Například zapsáno jako tice , existuje šest permutací množiny {1, 2, 3}, jmenovitě (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) a (3, 2, 1). Toto jsou všechna možná uspořádání této tříprvkové sady. Proměny jsou také přesmyčky slov, jejichž písmena jsou různá: písmena jsou již uspořádána v původním slově a přesmyčka je přeuspořádání písmen. Studium permutací konečných množin je důležitým tématem v oblasti kombinatoriky a teorie grup .

Permutace se používají téměř v každé oblasti matematiky a v mnoha dalších vědních oborech. V počítačové vědě se používají k analýze algoritmů řazení ; v kvantové fyzice , pro popis stavů částic; a v biologii pro popis sekvencí RNA .

Počet permutací n odlišných objektů je n  faktoriálů , obvykle zapsaných jako n ! , což znamená součin všech kladných celých čísel menších nebo rovných n .

Technicky je permutace množiny S definována jako bijekce od S k sobě. To znamená, že je to funkce od S do S, pro kterou se každý prvek vyskytuje jako hodnota obrázku přesně jednou . To souvisí s přeskupením prvků S, ve kterém je každý prvek s nahrazen odpovídajícím f ( s ) . Například výše uvedená permutace (3, 1, 2) je popsána funkcí definovanou jako ${\ displaystyle \ alpha}$

${\ Displaystyle \ alpha (1) = 3, \ quad \ alpha (2) = 1, \ quad \ alpha (3) = 2}$.

Kolekce všech permutací množiny tvoří skupinu nazývanou symetrická skupina množiny. Skupinová operace je kompozice (provádění dvou daných přeskupení za sebou), což má za následek další přeskupení. Protože vlastnosti permutací nezávisí na povaze nastavených prvků, často se při studiu permutací zvažují právě permutace sady . ${\ Displaystyle \ {1,2, \ ldots, n \}}$

V elementární kombinatorice jsou k -permutace nebo částečné permutace uspořádaná uspořádání k odlišných prvků vybraných ze sady. Pokud se k rovná velikosti sady, jedná se o permutace sady.

Dějiny

Permutace zvané hexagramy byly v Číně použity v I -ťingu ( Pchin -jin : Yi Jing) již v roce 1 000 př. N. L.

Al-Khalil (717–786), arabský matematik a kryptograf , napsal knihu kryptografických zpráv . Obsahuje první použití permutací a kombinací , seznam všech možných arabských slov se samohláskami i bez nich.

Pravidlo pro určení počtu permutací n objektů bylo v indické kultuře známé kolem roku 1150. Lilavati od indického matematika Bhaskary II obsahuje pasáž, která znamená:

Součinem násobení aritmetické řady začínajícího a zvyšujícího se jednotou a pokračujícího do počtu míst budou variace počtu s konkrétními čísly.

V roce 1677 Fabian Stedman popsal faktoriály při vysvětlování počtu permutací zvonů při změně vyzvánění . Počínaje dvěma zvony: „První, dva musí být přijaty třeba měnit dvěma způsoby“, kterou ilustruje tím, že ukazuje 1 2 a 2 1. Potom vysvětluje, že se třemi zvony existují „třikrát dvě postavy, které mají být vyrobeny z tři “, což je opět ilustrováno. Jeho vysvětlení zahrnuje „odhodit 3 a 1,2 zůstane; odhodit 2 a 1,3 zůstane; odhodit 1 a 2,3 zůstane“. Poté se přesune ke čtyřem zvonům a zopakuje hádání, které ukazuje, že budou existovat čtyři různé sady po třech. Ve skutečnosti se jedná o rekurzivní proces. Pokračuje pěti zvony metodou „casting away“ a tabeluje výsledných 120 kombinací. V tuto chvíli to vzdává a poznamenává:

Nyní je povaha těchto metod taková, že změny na jednom čísle chápou změny na všech nižších číslech, ... natolik, že se zdá, že komplementární Peal změn na jednom čísle je vytvořen spojením komplementárních Peals na všech nižších číslech do jednoho celého těla;

Stedman rozšiřuje zvažování permutací; dále zvažuje počet permutací písmen abecedy a koní ze stáje 20.

První případ, kdy byly pomocí permutací studovány zdánlivě nesouvisející matematické otázky, nastal kolem roku 1770, kdy Joseph Louis Lagrange při studiu polynomiálních rovnic pozoroval, že vlastnosti permutací kořenů rovnice souvisejí s možnostmi vyřešit. Tato řada prací nakonec vedla prostřednictvím práce Évariste Galoise v Galoisově teorii , která poskytuje úplný popis toho, co je možné a nemožné s ohledem na řešení polynomiálních rovnic (v jedné neznámé) radikály. V moderní matematice existuje mnoho podobných situací, ve kterých porozumění problému vyžaduje studium určitých permutací, které s ním souvisejí.

Permutace bez opakování

Nejjednodušším příkladem permutací jsou permutace bez opakování, kde uvažujeme počet možných způsobů uspořádání n položek do n míst. Factorial má zvláštní uplatnění při určování počet permutací v sadě, která neobsahuje opakování. Číslo n !, čti „n faktoriál“, je přesně tím způsobem, jak můžeme n věcí přeskupit do nového řádu. Máme -li například tři plody: pomeranč, jablko a hrušku, můžeme je sníst v uvedeném pořadí, nebo je můžeme změnit (například jablko, hruška a pak pomeranč). Přesný počet permutací je pak . S rostoucím počtem položek (n) se číslo extrémně zvyšuje. ${\ Displaystyle 3! = 1 \ cdot 2 \ cdot 3 = 6}$

Podobným způsobem je počet uspořádání r položek z n objektů považován za částečnou permutaci . Je zapsán jako (což znamená "n permute r") a je roven číslu (také zapsán jako ). ${\ displaystyle nPr}$${\ Displaystyle n (n-1) \ cdots (n-r+1)}$${\ displaystyle n!/(nr)!}$

Definice

V matematických textech je obvyklé označovat permutace pomocí malých řeckých písmen. Běžně se používá buď a , nebo a a . ${\ displaystyle \ alpha}$${\ displaystyle \ beta}$${\ Displaystyle \ sigma, \ tau}$${\ displaystyle \ pi}$

Permutace lze definovat jako bijekce ze sady S na sebe. Všechny permutace množiny s n prvky tvoří symetrickou skupinu , označenou , kde skupinovou operací je složení funkce . Pro dvě permutace a ve skupině tedy platí čtyři skupinové axiomy: ${\ displaystyle S_ {n}}$${\ displaystyle \ pi}$${\ Displaystyle \ sigma}$${\ displaystyle S_ {n}}$

1. Uzavření : Pokud a jsou v tom, tak je${\ displaystyle \ pi}$${\ Displaystyle \ sigma}$${\ displaystyle S_ {n}}$${\ Displaystyle \ pi \ sigma.}$
2. Asociativita : Pro jakékoli tři permutace ,${\ Displaystyle \ pi, \ sigma, \ tau \ v S_ {n}}$${\ Displaystyle (\ pi \ sigma) \ tau = \ pi (\ sigma \ tau).}$
3. Identita : Existuje permutace identity, označená a definovaná pro všechny . Pro všechny ,${\ displaystyle \ operatorname {id}}$${\ displaystyle \ operatorname {id} (x) = x}$${\ displaystyle x \ in S}$${\ displaystyle \ sigma \ v S_ {n}}$${\ displaystyle \ operatorname {id} \ sigma = \ sigma \ operatorname {id} = \ sigma.}$
4. Invertibilita : Pro každou permutaci existuje, takže${\ displaystyle \ pi \ v S_ {n}}$${\ Displaystyle \ pi ^{-1} \ v S_ {n}}$${\ Displaystyle \ pi \ pi ^{-1} = \ pi ^{-1} \ pi = \ jméno operátora {id}.}$

Složení dvou permutací obecně není komutativní , tj.${\ Displaystyle \ pi \ sigma \ neq \ sigma \ pi.}$

Jako bijekce od množiny k sobě je permutace funkcí, která provádí přeskupení množiny, a není sama přestavbou. Starším a elementárnějším hlediskem je, že permutace jsou samotné přestavby. Aby se tyto dva odlišily, identifikátory aktivní a pasivní jsou někdy předpony termínu permutace , zatímco ve starší terminologii se používají substituce a permutace .

Permutaci lze rozložit do jednoho nebo více nesouvislých cyklů , tj. Oběžných drah , které se nacházejí opakovaným sledováním aplikace permutace na některé prvky. Například permutace definovaná pomocí má 1 cyklus, zatímco permutace definovaná a má 2 cykly (podrobnosti o syntaxi viz § Zápis cyklu níže). Cyklus o délce k , tj. Skládající se z k prvků, se obecně nazývá k -cyklus. ${\ Displaystyle \ sigma}$${\ Displaystyle \ sigma (7) = 7}$${\ displaystyle (\, 7 \,)}$${\ displaystyle \ pi}$${\ displaystyle \ pi (2) = 3}$${\ displaystyle \ pi (3) = 2}$${\ Displaystyle (\, 2 \, 3 \,)}$

Prvek v 1 cyklu se nazývá pevný bod permutace. Permutace bez pevných bodů se nazývá odchylka . 2 cykly se nazývají transpozice ; takové permutace pouze vyměňují dva prvky, ostatní nechávají pevné. ${\ displaystyle (\, x \,)}$

Zápisy

Jelikož je psaní permutací elementární, tj. Jako funkce po částech , těžkopádné, bylo vynalezeno několik zápisů, které je reprezentují kompaktněji. Cyklická notace je oblíbenou volbou mnoha matematiků díky své kompaktnosti a skutečnosti, že zprůhledňuje strukturu permutace. Je to notace použitá v tomto článku, pokud není uvedeno jinak, ale jiné notace jsou stále široce používány, zejména v aplikačních oblastech.

Dvouřádkový zápis

V Cauchyova ‚s dvouřádkovým notaci , jeden seznam o prvcích S v první řadě, a pro každý z nich jeho obraz pod ním ve druhé řadě. Například konkrétní permutaci množiny S = {1, 2, 3, 4, 5} lze zapsat jako

${\ displaystyle \ sigma = {\ begin {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1 \ end {pmatrix}};}}$

to znamená, že σ splňuje σ (1) = 2 , σ (2) = 5 , σ (3) = 4 , σ (4) = 3 a σ (5) = 1 . Prvky S se mohou objevit v libovolném pořadí v první řadě. Tuto permutaci lze také zapsat jako:

${\ displaystyle \ sigma = {\ begin {pmatrix} 3 & 2 & 5 & 1 & 4 \\ 4 & 5 & 1 & 2 & 3 \ end {pmatrix}},}$

nebo

${\ displaystyle \ sigma = {\ begin {pmatrix} 5 & 1 & 4 & 3 & 2 \\ 1 & 2 & 3 & 4 & 5 \ end {pmatrix}}.}$

Jednořádkový zápis

Pokud existuje „přirozený“ řád pro prvky S , řekněme , pak to použijeme pro první řádek dvouřádkového zápisu: ${\ displaystyle x_ {1}, x_ {2}, \ ldots, x_ {n}}$

${\ Displaystyle \ sigma = {\ begin {pmatrix} x_ {1} & x_ {2} & x_ {3} & \ cdots & x_ {n} \\\ sigma (x_ {1}) & \ sigma (x_ {2}) & \ sigma (x_ {3}) & \ cdots & \ sigma (x_ {n}) \ end {pmatrix}}.}$

Za tohoto předpokladu lze vynechat první řádek a zapsat permutaci do jednořádkového zápisu jako

${\ Displaystyle (\ sigma (x_ {1}) \; \ sigma (x_ {2}) \; \ sigma (x_ {3}) \; \ cdots \; \ sigma (x_ {n}))}$,

tj. uspořádané uspořádání S. Je třeba dbát na rozlišení jednořádkového zápisu od zápisu cyklu popsaného níže. V matematické matematice je běžným zvykem vynechat závorky pro jednořádkovou notaci a používat je pro cyklickou notaci. Jednořádkový zápis se také nazývá slovní reprezentace permutace. Výše uvedený příklad by pak byl 2 5 4 3 1, protože pro první řádek by byl předpokládán přirozený řád 1 2 3 4 5 . (Je typické používat čárky k oddělení těchto záznamů, pouze pokud některé mají dvě nebo více číslic.) Tato forma je kompaktnější a je běžná v elementární kombinatorice a informatice . Je to zvláště užitečné v aplikacích, kde mají být prvky S nebo permutace porovnávány jako větší nebo menší.

Zápis cyklu

Cyklická notace popisuje účinek opakovaného použití permutace na prvky sady. Vyjadřuje permutaci jako součin cyklů ; protože různé cykly jsou disjunktní , toto se označuje jako „rozklad na disjunktní cykly“.

Chcete -li zapsat permutaci do notace cyklu, postupujte takto: ${\ Displaystyle \ sigma}$

1. Napsat otvor konzola zvolit libovolný prvek x a a zapište:${\ displaystyle S}$${\ displaystyle (\, x}$
2. Potom sledujte oběžnou dráhu x ; to znamená, zapište si jeho hodnoty pod postupné aplikace :${\ Displaystyle \ sigma}$${\ Displaystyle (\, x \, \ sigma (x) \, \ sigma (\ sigma (x)) \, \ ldots}$
3. Opakujte, dokud se hodnota nevrátí k x, a zapište si místo x koncovou závorku :${\ Displaystyle (\, x \, \ sigma (x) \, \ sigma (\ sigma (x)) \, \ ldots \,)}$
4. Nyní pokračovat s prvkem y z S , ještě není napsáno, a postupovat stejným způsobem:${\ Displaystyle (\, x \, \ sigma (x) \, \ sigma (\ sigma (x)) \, \ ldots \,) (\, y \, \ ldots \,)}}$
5. Opakujte, dokud nejsou všechny prvky S zapsány v cyklech.

Protože pro každý nový cyklus lze počáteční bod zvolit různými způsoby, existuje obecně mnoho různých zápisů cyklu pro stejnou permutaci; pro výše uvedený příklad má:

${\ Displaystyle {\ begin {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1 \ end {pmatrix}} = (\, 1 \, 2 \, 5 \,) (\, 3 \, 4 \,) = (\, 3 \, 4 \,) (\, 1 \, 2 \, 5 \,) = (\, 4 \, 3 \,) (\, 2 \, 5 \, 1 \,) = (\, 3 \, 4 \ ,) (\, 5 \, 1 \, 2 \,).}$

1-cykly jsou často vynechány ze zápisu cyklu za předpokladu, že je jasný kontext; pro jakýkoli prvek x v S, který se neobjevuje v žádném cyklu, implicitně předpokládá . Identita permutace , který se skládá pouze z 1-cyklů, mohou být označeny jedním 1-cyklu (x), a číslo 1 nebo id . ${\ Displaystyle \ sigma (x) = x}$

Vhodnou vlastností zápisu cyklu je, že lze najít inverzní permutaci jednoduše obrácením pořadí prvků v cyklech permutace. Například

${\ Displaystyle [(\, 1 \, 2 \, 5 \,) (\, 3 \, 4 \,)]^{-1} = (\, 5 \, 2 \, 1 \,) (\, 4 \, 3 \,)}$

Kanonický zápis cyklu

V některých kombinatorických kontextech je užitečné stanovit určité pořadí prvků v cyklech a samotných (disjunktních) cyklů. Miklós Bóna nazývá následující možnosti uspořádání kanonickým zápisem cyklu :

• v každém cyklu je největší prvek uveden jako první
• cykly jsou řazeny ve vzestupném pořadí podle jejich prvního prvku

Například (312) (54) (8) (976) je permutace v kanonickém zápisu cyklu. Kanonický zápis cyklu nevynechává jednocykly.

Richard P. Stanley nazývá stejnou volbu reprezentace „standardní reprezentací“ permutace. a Martin Aigner pro stejný pojem používá termín „standardní forma“. Sergey Kitaev také používá terminologii „standardní formy“, ale obrací obě možnosti; to znamená, že každý cyklus uvádí nejprve svůj nejmenší prvek a cykly jsou seřazeny v sestupném pořadí podle jejich nejmenších, tj. prvních prvků.

Složení permutací

Složení dvou permutací lze označit dvěma způsoby. je funkce, která mapuje jakýkoli prvek x sady na . Permutace úplně vpravo se na argument aplikuje jako první, kvůli způsobu, jakým je aplikace funkce napsána. ${\ Displaystyle \ sigma \ cdot \ pi}$${\ Displaystyle \ sigma (\ pi (x))}$

Vzhledem k tomu, funkce složení je asociativní , takže je provozování prostředku na permutací: . Proto jsou produkty s více než dvěma permutacemi obvykle zapsány bez přidání závorek k expresnímu seskupení; bývají také psány bez tečky nebo jiného znaku označujícího kompozici. ${\ Displaystyle (\ sigma \ pi) \ tau = \ sigma (\ pi \ tau)}$

Někteří autoři dávají přednost tomu, aby nejprve působil faktor úplně vlevo, ale za tímto účelem musí být permutace zapsány napravo od jejich argumentu, často jako exponent, kde σ působící na x je psáno x ^σ ; pak je součin definován x ^{σ · π} = ( x ^σ ) ^π . To však dává jiné pravidlo pro znásobení permutací; tento článek používá definici, kde je nejprve použita pravá permutace.

Další použití termínu permutace

Koncept permutace jako uspořádaného uspořádání připouští několik generalizací, které nejsou permutacemi, ale v literatuře se jim říká permutace.

k -permutace n

Slabší význam pojmu permutace , někdy používaný v textech elementární kombinatoriky, označuje ta uspořádaná uspořádání, ve kterých se žádný prvek nevyskytuje více než jednou, ale bez požadavku na použití všech prvků z dané množiny. Nejde o permutace s výjimkou zvláštních případů, ale o přirozené zobecnění konceptu uspořádaného uspořádání. Ve skutečnosti toto použití často zahrnuje zvažování uspořádání pevné délky  k prvků převzatých z dané sady velikosti n , jinými slovy, tyto k -permutace n jsou různá uspořádaná uspořádání podmnožiny k -prvku n -sady ( ve starší literatuře se jim někdy říká variace nebo úpravy ). Tyto objekty jsou také známé jako částečné permutace nebo jako sekvence bez opakování , termíny, které se vyhýbají záměně s jiným, běžnějším, významem „permutace“. Počet těchto -permutations z je označován různě takovými symbolech, , , , , nebo , a jeho hodnota je dána součinem ${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle P_ {k}^{n}}$${\ displaystyle _ {n} P_ {k}}$${\ displaystyle ^{n} P_ {k}}$${\ displaystyle P_ {n, k}}$${\ Displaystyle P (n, k)}$

${\ Displaystyle P (n, k) = \ underbrace {n \ cdot (n-1) \ cdot (n-2) \ cdots (n-k+1)} _ {k \ \ mathrm {faktory}}}$,

což je 0, když k > n , a jinak se rovná

${\ displaystyle {\ frac {n!} {(nk)!}}.}$

Produkt je dobře definován bez předpokladu, že jde o nezáporné celé číslo a má význam i mimo kombinatoriku; je známý jako symbol Pochhammer nebo jako tý padajícího faktoriálu síly z . ${\ displaystyle n}$ ${\ displaystyle (n) _ {k}}$${\ displaystyle k}$${\ displaystyle n^{\ podtržení {k}}}$${\ displaystyle n}$

Toto použití pojmu permutace úzce souvisí s pojmem kombinace . K -element Kombinace n -Set S je k prvek podmnožina S , prvky, které nejsou objednal. Tím, že všechny k podmnožiny elementu S a objednávání každý z nich ve všech možných směrech, získáme všechny K -permutations ze S . Počet k- -combinations o s n -Set, C ( n , k ), se proto vztahuje k počtu k- -permutations z n tím, že:

${\ Displaystyle C (n, k) = {\ frac {P (n, k)} {P (k, k)}} = = \ \ frac {\ tfrac {n!} {(nk)!}} {\ tfrac {k!} {0!}}} = {\ frac {n!} {(nk)! \, k!}}.}$

Tato čísla jsou také známá jako binomické koeficienty a jsou označována . ${\ displaystyle {\ binom {n} {k}}}$

Permutace s opakováním

Uspořádané uspořádání n prvků sady S , kde je povoleno opakování, se nazývá n -tuples . Někdy byly označovány jako permutace s opakováním , i když nejsou obecně permutacemi. V některých kontextech se jim také říká slova nad abecedou S. V případě, že množina S má k prvků, počet n -tuples přes S je Neexistuje žádné omezení na tom, jak často se prvek může objevit v n -tuple, ale pokud omezení jsou umístěny na tom, jak často se může objevit prvek, tento vzorec je není nadále platný. ${\ Displaystyle k^{n}.}$

Permutace více sad

Pokud M je konečná multimnožina , pak multimnožina permutace je uspořádaná uspořádání prvků M , ve kterých se každý prvek několikrát roven přesně do své mnohosti v M . Přesmyčka ze slova, která má několik opakovaných písmen je příkladem multiset permutace. V případě, že multiplicity z prvků M (vzít v některých pořadí) jsou , , ..., a jejich součet (to znamená, že velikost M ) je N , pak počet Multiset permutací M je dán multinomiálního koeficientem , ${\ displaystyle m_ {1}}$${\ displaystyle m_ {2}}$${\ displaystyle m_ {l}}$

${\ Displaystyle {n \ choose m_ {1}, m_ {2}, \ ldots, m_ {l}} = {\ frac {n!} {m_ {1}! \, m_ {2}! \, \ cdots \, m_ {l}!}} = {\ frac {\ left (\ sum _ {i = 1}^{l} {m_ {i}} \ right)!} {\ prod _ {i = 1}^ {l} {m_ {i}!}}}.}$

Například počet různých anagramů slova MISSISSIPPI je:

${\ displaystyle {\ frac {11!} {1! \, 4! \, 4! \, 2!}} = 34650}$.

K -permutation z Multiset M je sekvence délky k prvků M , ve kterém se každý prvek několikrát menší než nebo se rovná její mnohosti v M (prvek, je počet opakování ).

Kruhové permutace

Permutace, pokud jsou považovány za uspořádání, se někdy označují jako lineárně uspořádaná uspořádání. V těchto uspořádáních je první prvek, druhý prvek atd. Pokud jsou však objekty uspořádány kruhově, toto rozlišující uspořádání již neexistuje, to znamená, že v uspořádání není žádný „první prvek“, lze jakýkoli prvek považovat za začátek uspořádání. Uspořádání objektů kruhovým způsobem se nazývá kruhové permutace . Ty mohou být formálně definovány jako třídy ekvivalence běžných permutací objektů pro vztah ekvivalence generovaný přesunutím konečného prvku lineárního uspořádání na jeho přední stranu.

Dvě kruhové permutace jsou ekvivalentní, pokud lze jednu otočit do druhé (tj. Cyklovat bez změny relativních poloh prvků). Následující čtyři kruhové permutace na čtyřech písmenech jsou považovány za stejné.

     1           4           2           3
   4   3       2   1       3   4       1   2
     2           3           1           4

Kruhová uspořádání je třeba číst proti směru hodinových ručiček, takže následující dvě nejsou ekvivalentní, protože žádná rotace nemůže přivést jedno k druhému.

     1          1
   4   3      3   4
     2          2

Počet kruhových permutací množiny S s n prvky je ( n  - 1) !.

Vlastnosti

Počet permutací n odlišných objektů je n !.

Počet n -permutací s k disjunktních cyklů je Stirlingovo číslo bez znaménka prvního druhu , označené c ( n , k ) .

Typ permutace

Cykly permutačního oddílu množina tak délek cyklů permutace tvoří oddíl z n nazývá typ cyklu o . V typu cyklu je „1“ pro každý pevný bod σ, „2“ pro každou transpozici atd. Typ cyklu je (3, 2, 2, 1). Toto může být také zapsáno v kompaktnější formě jako [1 ¹ 2 ² 3 ¹ ]. ${\ displaystyle S_ {n}}$${\ Displaystyle \ sigma}$${\ Displaystyle \ sigma}$${\ Displaystyle \ beta = (\, 1 \, 2 \, 5 \,) (\, 3 \, 4 \,) (6 \, 8 \,) (\, 7 \,)}$

Obecná forma je , kde jsou počty cyklů příslušné délky. Počet permutací určitého typu je ${\ Displaystyle [1^{\ alpha _ {1}} 2^{\ alpha _ {2}} \ dotsm n^{\ alpha _ {n}}]}$${\ Displaystyle \ alpha _ {1}, \ ldots, \ alpha _ {n}}$

${\ Displaystyle {\ frac {n!} {1^{\ alpha _ {1}} 2^{\ alpha _ {2}} \ dotsm n^{\ alpha _ {n}} \ alpha _ {1}! \ alpha _ {2}! \ dotsm \ alpha _ {n}!}}}$.

Konjugace permutací

Obecně platí, že skládání permutací zapsaných v cyklické notaci se nesleduje žádným snadno popsatelným vzorem - cykly kompozice se mohou lišit od těch, které se skládají. Struktura cyklu je však zachována ve zvláštním případě konjugace permutace jinou permutací , což znamená vytvoření produktu . Odtud je konjugovaná of a její cyklus zápis může být dosaženo tím, že notaci cyklus pro i použití pro všechny položky v něm. Z toho vyplývá, že dvě permutace jsou konjugovány přesně, když mají stejný typ. ${\ Displaystyle \ sigma}$${\ displaystyle \ pi}$${\ Displaystyle \ pi \ sigma \ pi ^{-1}}$${\ Displaystyle \ pi \ sigma \ pi ^{-1}}$${\ Displaystyle \ sigma}$${\ Displaystyle \ sigma}$${\ displaystyle \ pi}$

Pořadí povolení

Pořadí permutace je nejmenší kladné celé číslo m, takže . Je to nejmenší společný násobek jeho délek cyklů. Například pořadí je . ${\ Displaystyle \ sigma}$${\ Displaystyle \ sigma ^{m} = \ mathrm {id}}$${\ Displaystyle (\, 1 \, 3 \, 2) (\, 4 \, 5 \,)}$${\ Displaystyle 2 \ cdot 3 = 6}$

Parita permutace

Každá permutace konečné sady může být vyjádřena jako součin transpozic. Ačkoli pro danou permutaci může existovat mnoho takových výrazů, buď všechny obsahují sudý nebo lichý počet transpozic. V závislosti na tomto čísle lze tedy všechny permutace klasifikovat jako sudé nebo liché .

Tento výsledek lze rozšířit tak , aby každé permutaci přiřadil napsaný znak . jestli je sudý a jestli lichý. Pak pro dvě permutace a${\ displaystyle \ operatorname {sgn} \ sigma}$${\ displaystyle \ operatorname {sgn} \ sigma =+1}$${\ Displaystyle \ sigma}$${\ displaystyle \ operatorname {sgn} \ sigma = -1}$${\ Displaystyle \ sigma}$${\ Displaystyle \ sigma}$${\ displaystyle \ pi}$

${\ displaystyle \ operatorname {sgn} (\ sigma \ pi) = \ operatorname {sgn} \ sigma \ cdot \ operatorname {sgn} \ pi.}$

Z toho vyplývá, že ${\ displaystyle \ operatorname {sgn} \ left (\ sigma \ sigma ^{-1} \ right) =+1.}$

Maticová reprezentace

Permutace matice je n x n matice , která má přesně jedné položky 1 v každém sloupci a v každém řádku, a všechny ostatní položky jsou 0. Existuje několik různých konvence, které lze použít k přiřazení permutační matrice na permutací {1 , 2, ..., n }. Jedním přirozeným přístupem je přiřadit k permutaci σ matici, jejíž ( i , j ) vstup je 1, pokud i = σ ( j ) a je 0, jinak. Tato konvence má dvě atraktivní vlastnosti: za prvé, součin matic a permutací je ve stejném pořadí, to znamená pro všechny permutace σ a π . Za druhé, pokud představuje standardní sloupcový vektor (vektor s i -tou položkou rovnou 1 a všechny ostatní položky rovnou 0), pak . ${\ displaystyle M _ {\ sigma}}$${\ Displaystyle M _ {\ sigma} M _ {\ pi} = M _ {\ sigma \ circ \ pi}}$${\ displaystyle {\ bf {e}} _ {i}}$ ${\ displaystyle n \ times 1}$ ${\ Displaystyle M _ {\ sigma} {\ bf {e}} _ {i} = {\ bf {e}} _ {\ sigma (i)}}$

U této konvence například matice spojená s permutací je a matice spojená s permutací je . Potom je složení permutací a odpovídající maticový produkt je ${\ Displaystyle \ sigma (1,2,3) = (2,1,3)}$${\ displaystyle {\ begin {pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \ end {pmatrix}}}$${\ Displaystyle \ pi (1,2,3) = (2,3,1)}$${\ displaystyle {\ begin {pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \ end {pmatrix}}}$${\ Displaystyle (\ sigma \ circ \ pi) (1,2,3) = \ sigma (2,3,1) = (1,3,2)}$

V literatuře je také běžné najít inverzní konvenci, kde je permutace σ spojena s maticí, jejíž ( i , j ) vstup je 1, pokud j = σ ( i ) a je 0 jinak. V této konvence se permutační matice množí v opačném pořadí než permutace, to znamená pro všechny permutace σ a π . V této korespondenci působí permutační matice permutací indexů standardních řádkových vektorů : jeden má . ${\ Displaystyle P _ {\ sigma} = (M _ {\ sigma})^{-1} = (M _ {\ sigma})^{T}}$${\ Displaystyle P _ {\ sigma} P _ {\ pi} = P _ {\ pi \ circ \ sigma}}$${\ displaystyle 1 \ times n}$${\ displaystyle ({\ bf {e}} _ {i})^{T}}$${\ Displaystyle ({\ bf {e}} _ {i})^{T} P _ {\ sigma} = ({\ bf {e}} _ {\ sigma (i)})^{T}}$

Cayley tabulky vpravo se zobrazují tyto matrice pro permutace 3 elementů.

Foatovo přechodové lemma

Existuje vztah mezi jednořádkovým a kanonickým cyklickým zápisem. Uvažujme permutaci , v kanonickém cyklickém zápisu, pokud smažeme jeho závorky cyklu, získáme permutaci v jednořádkové notaci. Foatovo přechodové lemma stanoví povahu této korespondence jako bijekce na množinu n -permutací (pro sebe). Richard P. Stanley nazývá tuto korespondenci zásadní bijekcí . ${\ Displaystyle (\, 2 \,) (\, 3 \, 1 \,)}$${\ Displaystyle (2,3,1)}$

Nechť je transformace vymazávající závorky. Inverzní funkce je o něco méně intuitivní. Počínaje jednořádkovým zápisem musí první cyklus v kanonickém zápisu cyklu začínat . Dokud jsou následující prvky menší než , jsme ve stejném cyklu. Druhý cyklus začíná na nejmenším indexu , takže . Jinými slovy, je větší než všechno ostatní nalevo, takže se tomu říká maximum zleva doprava . Každý cyklus v kanonickém zápisu cyklu začíná maximem zleva doprava. ${\ displaystyle f}$${\ Displaystyle q = f (p)}$${\ Displaystyle q = q_ {1} q_ {2} \ cdots q_ {n}}$${\ displaystyle q_ {1}}$${\ displaystyle q_ {1}}$${\ displaystyle j}$${\ displaystyle q_ {j}> q_ {1}}$${\ displaystyle q_ {j}}$

Například v jednořádkovém zápisu je 5 první prvek větší než 3, takže první cyklus musí být . Pak 8 je další prvek větší než 5, takže druhý cyklus je . Protože 9 je větší než 8, je to samotný cyklus. Nakonec je 9 větší než všechny zbývající prvky napravo, takže poslední cyklus je . ${\ Displaystyle (3,1,2,5,4,8,9,7,6)}$${\ displaystyle (\, 3 \, 1 \, 2 \,)}}$${\ displaystyle (\, 5 \, 4 \,)}$${\ displaystyle (\, 8 \,)}$${\ Displaystyle (\, 9 \, 7 \, 6 \,)}}$

Šest permutací s jejich cyklickými mapami je , kde jsou cyklické mapy určeny podle velikosti cyklu a pokračují ve směru hodinových ručiček. ${\ displaystyle 123}$${\ Displaystyle 123 (1) (2) (3), 132 (1) (32), 213 (3) (21), 231 (231), 312 (312), 321 (2) (13)}$

Jako první důsledek, počet n-permutací s přesně k zleva doprava maxim je také, který se rovná signless Stirling číslo prvního druhu , . Foataovo mapování dále trvá n -permutaci s k -slabými excesy na n -permutací s k -1 výstupy. Například (2) (31) = 321 má dvě slabé úrovně (v indexu 1 a 2), zatímco f (321) = 231 má jeden výstup (v indexu 1; to znamená od 2 do 3). ${\ Displaystyle c (n, k)}$

Permutace zcela seřazených sad

V některých aplikacích budou prvky permutované sady navzájem porovnávány. To vyžaduje, aby množina S měla celkové pořadí, aby bylo možné porovnávat libovolné dva prvky. Sada {1, 2, ..., n } je zcela seřazena podle obvyklého vztahu „≤“, a proto je v těchto aplikacích nejčastěji používanou sadou, ale obecně bude stačit jakákoli zcela seřazená sada. V těchto aplikacích je k uspořádání pozic v permutaci potřeba uspořádaný pohled na uspořádání permutace.

Existuje celá řada vlastností, které mají přímý vztah k celkovému uspořádání S .

Stoupání, klesání, běhy a excesy

Výstupu z permutačního  å o n je libovolná poloha i  <  n , kde následující hodnota je větší, než je současný. To znamená, že pokud σ  =  σ ₁ σ ₂ ... σ _n , pak i je výstup, pokud σ _i  <  σ _{i +1} .

Například permutace 3452167 má stoupání (v pozicích) 1, 2, 5 a 6.

Podobně sestup je poloha i  <  n s σ _i  >  σ _{i +1} , takže každé i s buď je výstupem nebo je sestupem  σ . ${\ Displaystyle 1 \ leq i <n}$

Vzestupně spustit z permutací je neprázdná rostoucí souvislé subsekvenci permutace, které nemohou být prodloužena na obou koncích; odpovídá maximální sekvenci po sobě jdoucích výstupů (ten může být prázdný: mezi dvěma po sobě následujícími sestupy stále existuje vzestupný běh délky 1). Naproti tomu rostoucí subsekvence permutace nemusí nutně sousedit: je to rostoucí sekvence prvků získaných z permutace vynecháním hodnot v některých polohách. Například permutace 2453167 má vzestupné cykly 245, 3 a 167, zatímco má rostoucí podsekvenci 2367.

Pokud má permutace k  - 1 sestupů, pak to musí být spojení k vzestupných běhů.

Počet permutací n s k výstupy je (podle definice) eulerovské číslo ; toto je také počet permutací n s k sestupy. Někteří autoři však definují eulerovské číslo jako počet permutací s k vzestupnými cykly, což odpovídá k - 1 sestupům. ${\ Displaystyle \ textstyle \ left \ langle {n \ atop k} \ right \ rangle}$${\ Displaystyle \ textstyle \ left \ langle {n \ atop k} \ right \ rangle}$

Excesance permutace σ ₁ σ ₂ ... σ _n je index j takový, že σ _j > j . Pokud nerovnost není přísná (tj. Σ _j ≥ j ), pak se j nazývá slabý exces . Počet n -permutací s k excese se shoduje s počtem n -permutací s k sestupně .

Inverze

Inverze z permutačního  å je dvojice ( i , j ) z polohy, kde jsou záznamy z permutací v pořadí opačném: a . Sjezd je tedy jen inverze na dvou sousedních pozicích. Například permutace σ = 23154 má tři inverze: (1, 3), (2, 3) a (4, 5) pro dvojice položek (2, 1), (3, 1) a ( 5, 4). ${\ Displaystyle i <j}$${\ Displaystyle \ sigma _ {i}> \ sigma _ {j}}$

Někdy je inverze definována jako dvojice hodnot ( σ _i , σ _j ), jejichž pořadí je obráceno; na počtu inverzí to nezáleží a tento pár (obrácený) je také inverzí ve výše uvedeném smyslu pro inverzní permutaci σ ⁻¹ . Počet inverzí je důležitým měřítkem toho, do jaké míry jsou položky permutace mimo provoz; je to stejné pro σ i pro σ ⁻¹ . Uspořádání permutace s k inverzemi k (tj. Její transformace na permutaci identity) postupným aplikováním sousedních transpozic (pravé vynásobení) je vždy možné a vyžaduje sekvenci k takových operací. Navíc bude fungovat jakákoli rozumná volba pro sousední transpozice: stačí zvolit v každém kroku transpozici i a i + 1, kde i je sestup permutace, jak byl dosud upraven (takže transpozice odstraní tento konkrétní sestup, ačkoli to může vytvořit další sestupy). Je tomu tak proto, že použití takové transpozice snižuje počet inverzí o 1; dokud toto číslo není nula, permutace není identita, takže má alespoň jedno klesání. Řazení bublin a třídění vkládáním lze interpretovat jako konkrétní instance tohoto postupu k uvedení pořadí do pořádku. Tento postup mimochodem dokazuje, že jakoukoli permutaci σ lze zapsat jako součin sousedních transpozic; protože toto může jednoduše obrátit jakoukoli sekvenci takových transpozic, která transformuje σ na identitu. Ve skutečnosti výčtem všech sekvencí sousedních transpozic, které by transformovaly σ na identitu, se získá (po obrácení) úplný seznam všech výrazů psaní minimální délky σ jako produktu sousedních transpozic.

Počet permutací n s k inverzemi k je vyjádřen mahonským číslem, je to koeficient X ^k v expanzi součinu

${\ Displaystyle \ prod _ {m = 1}^{n} \ sum _ {i = 0}^{m-1} X^{i} = 1 \ left (1+X \ right) \ left (1+ X+X^{2} \ right) \ cdots \ left (1+X+X^{2}+\ cdots+X^{n-1} \ right),}$

který je také známý (s q nahrazeným X ) jako q-faktoriál [ n ] _q ! . Rozšíření produktu se objeví v náhrdelníku (kombinatorika) .

Permutace ve výpočetní technice

Proměny číslování

Jedním ze způsobů, jak reprezentovat permutace n, je celé číslo N s 0 ≤  N  <  n ! Za předpokladu, že jsou uvedeny pohodlné metody pro převod mezi číslem a reprezentací permutace jako uspořádaného uspořádání (sekvence). To poskytuje nejkompaktnější reprezentaci libovolných permutací a při práci na počítači je obzvláště atraktivní, když n je dostatečně malé, aby N bylo možné držet ve strojovém slově; pro 32bitová slova to znamená n  ≤ 12 a pro 64bitová slova to znamená n  ≤ 20. Převod lze provést prostřednictvím přechodné formy posloupnosti čísel d _n , d _{n −1} , ..., d ₂ , d ₁ , kde d _i je nezáporné celé číslo menší než i ( d ₁ lze vynechat , protože je vždy 0, ale jeho přítomnost usnadňuje popis následné konverze na permutaci). Prvním krokem je pak jednoduše vyjádřit N v systému faktoriálních čísel , což je jen konkrétní smíšená radixová reprezentace, kde pro čísla až n ! základy pro postupné číslice jsou n , n - 1 , ..., 2, 1. Druhý krok interpretuje tuto sekvenci jako Lehmerův kód nebo (téměř ekvivalentně) jako inverzní tabulku.

Rotheův diagram pro ${\ Displaystyle \ sigma = (6,3,8,1,4,9,7,2,5)}$

σ i já	1	2	3	4	5	6	7	8	9	Lehmerův kód
1	×	×	×	×	×	•				d 9 = 5
2	×	×	•							d 8 = 2
3	×	×		×	×		×	•		d 7 = 5
4	•									d 6 = 0
5		×		•						d 5 = 1
6		×			×		×		•	d 4 = 3
7		×			×		•			d 3 = 2
8		•								d 2 = 0
9					•					d 1 = 0
Inverzní tabulka	3	6	1	2	4	0	2	0	0

V Lehmerově kódu pro permutaci  σ číslo d _n představuje volbu provedenou pro první člen  σ ₁ , číslo d _{n −1} představuje volbu provedenou pro druhý člen σ ₂ mezi zbývajícími n - 1 prvky množiny , a tak dále. Přesněji, každé d _{n +1− i} udává počet zbývajících prvků striktně menší než termín σ _i . Protože se tyto zbývající prvky musí objevit jako pozdější termín σ _j , číslice d _{n +1− i} počítá inverze ( i , j ) zahrnující i jako menší index (počet hodnot j, pro které i  <  j a σ _i  >  σ _j ). Inverze tabulka pro  å je velmi podobná, ale zde d _{n + 1- K} počítá počet inverzí ( i , j ), kde k  =  σ _j dochází v menší ze dvou hodnot uvedených v obrácené pořadí. Obě kódování lze zobrazit pomocí Rotheova diagramu n  by  n (pojmenovaného podle Heinricha Augusta Rotheho ), ve kterém tečky na ( i , σ _i ) označují položky permutace a kříž na ( i , σ _j ) označuje inverzi ( i , j ); podle definice inverzí se kříž objeví v jakémkoli čtverci, který přichází jak před tečkou ( j , σ _j ) ve svém sloupci, tak před tečkou ( i , σ _i ) v jejím řádku. Kód Lehmer uvádí počty křížků v po sobě jdoucích řádcích, zatímco inverzní tabulka uvádí počty křížků v následných sloupcích; je to jen Lehmerův kód pro inverzní permutaci a naopak.

Chcete -li efektivně převést Lehmerův kód d _n , d _{n −1} , ..., d ₂ , d ₁ na permutaci uspořádané množiny S , je možné začít se seznamem prvků S ve vzestupném pořadí a pro i rostoucí z 1 na n nastavte σ _i na prvek v seznamu, kterému předchází d _{n +1− i} ostatní, a odeberte tento prvek ze seznamu. Chcete -li převést inverzní tabulku d _n , d _{n −1} , ..., d ₂ , d ₁ na odpovídající permutaci, je možné procházet čísla od d ₁ do d _n při vkládání prvků S od největšího po nejmenší do zpočátku prázdná sekvence; v kroku s použitím čísla d z inverzní tabulky byl prvek ze S vložen do posloupnosti v místě, kde mu předcházejí d prvky již přítomné. Alternativně lze zpracovat čísla z inverzní tabulky a prvky S v opačném pořadí, počínaje řadou n prázdných slotů, a v každém kroku umístit prvek ze S do prázdného slotu, kterému předchází d další prázdné pole sloty.

Převod po sobě jdoucích přirozených čísel na systém faktoriálních čísel produkuje tyto sekvence v lexikografickém pořadí (jako je tomu u jakéhokoli smíšeného radixového číselného systému) a jejich další převod na permutace zachovává lexikografické uspořádání za předpokladu, že je použita interpretace kódu Lehmer (pomocí inverzních tabulek) , dostane se jiné uspořádání, kde se začíná porovnáním permutací podle místa jejich položek 1, nikoli podle hodnoty jejich prvních záznamů). Součet čísel v reprezentaci faktoriálního číselného systému udává počet inverzí permutace a parita tohoto součtu udává podpis permutace. Navíc polohy nul v inverzní tabulce udávají hodnoty maxima permutace zleva doprava (v příkladu 6, 8, 9), zatímco polohy nul v Lehmerově kódu jsou pozice vpravo -minima vlevo (v příkladových polohách 4, 8, 9 hodnot 1, 2, 5); to umožňuje vypočítat distribuci takových extrémů mezi všechny permutace. Permutace s Lehmerovým kódem d _n , d _{n −1} , ..., d ₂ , d ₁ má stoupání n - i právě tehdy, když d _i ≥ d _i+1 .

Algoritmy pro generování permutací

Při práci na počítači může být vyžadováno generování permutací dané sekvence hodnot. Metody, které jsou k tomu nejlépe přizpůsobeny, závisí na tom, zda chcete nějaké náhodně zvolené permutace, nebo všechny permutace, a ve druhém případě, zda je vyžadováno konkrétní uspořádání. Další otázkou je, zda má být vzata v úvahu možná rovnost mezi položkami v dané posloupnosti; pokud ano, měli bychom generovat pouze odlišné vícesetové permutace sekvence.

Zjevným způsobem, jak generovat permutace n, je generovat hodnoty pro Lehmerův kód (případně pomocí reprezentace celých čísel faktoriálního systému celých čísel až n !) A převést je na odpovídající permutace. Tento druhý krok, i když je přímočarý, je však obtížně efektivně implementovatelný, protože vyžaduje n operací, každý z výběru ze sekvence a vymazání z ní, v libovolné poloze; zjevných reprezentací sekvence jako pole nebo propojeného seznamu , oba vyžadují (z různých důvodů) asi n ² /4 operací k provedení převodu. Vzhledem k tomu, že n bude pravděpodobně poměrně malé (zvláště pokud je zapotřebí generování všech permutací), není to příliš velký problém, ale ukazuje se, že jak pro náhodné, tak pro systematické generování existují jednoduché alternativy, které jsou podstatně lepší. Z tohoto důvodu se nezdá užitečné, i když určitě možné, použít speciální datovou strukturu, která by umožnila provedení převodu z Lehmerova kódu na permutaci v čase O ( n log n ) .

Náhodné generování permutací

Pro generování náhodných permutací dané sekvence n hodnot nezáleží na tom, zda člověk použije na sekvenci náhodně vybranou permutaci n , nebo zvolí náhodný prvek ze sady odlišných (více sad) permutací sekvence. Důvodem je, že i když v případě opakovaných hodnot může existovat mnoho odlišných permutací n, které vedou ke stejné permutované sekvenci, počet těchto permutací je stejný pro každý možný výsledek. Na rozdíl od systematického generování, které se pro velké n stane nerealizovatelným kvůli růstu čísla n !, Není důvod předpokládat, že n bude pro náhodné generování malé.

Základní myšlenkou generování náhodné permutace je generovat náhodně jednu z n ! sekvence celých čísel d ₁ , d ₂ , ..., d _n splňující 0 ≤ d _i < i (protože d ₁ je vždy nula, lze vynechat) a převést jej na permutaci prostřednictvím bijektivní korespondence. U druhé korespondence by bylo možné (reverzní) sekvenci interpretovat jako Lehmerův kód, a to dává generační metodu, kterou poprvé publikovali v roce 1938 Ronald Fisher a Frank Yates . Zatímco v té době nebyla počítačová implementace problémem, tato metoda trpí obtížemi načrtnutými výše pro efektivní převod z kódu Lehmer na permutaci. To lze napravit použitím jiné bijektivní korespondence: po použití d _i k výběru prvku mezi i zbývajícími prvky sekvence (pro snížení hodnot i ), místo odstranění prvku a zhutnění sekvence posunutím dolů o další prvky o jedno místo dolů , jeden zamění prvek s posledním zbývajícím prvkem. Prvky zbývající pro výběr tedy tvoří po sobě jdoucí rozsah v každém časovém bodě, přestože se nemusí vyskytovat ve stejném pořadí, jako tomu bylo v původní sekvenci. Mapování ze sekvence celých čísel na permutace je poněkud komplikované, ale je vidět, že produkuje každou permutaci přesně jedním způsobem, okamžitou indukcí . Když se stane vybraný prvek posledním zbývajícím prvkem, operaci swap lze vynechat. To se nevyskytuje dostatečně často, aby bylo zaručeno testování podmínky, ale konečný prvek musí být zahrnut mezi kandidáty výběru, aby bylo zaručeno, že lze vygenerovat všechny permutace.

Výsledný algoritmus pro generování náhodné permutace lze v pseudokódu popsat následovně : a[0], a[1], ..., a[n − 1]

for i from n downto 2 do
    di ← random element of { 0, ..., i − 1 }
    swap a[di] and a[i − 1]

To lze kombinovat s inicializací pole následujícím způsobem a[i] = i

for i from 0 to n−1 do
    di+1 ← random element of { 0, ..., i }
    a[i] ← a[di+1]
    a[di+1] ← i

Pokud d _{i +1} = i , první přiřazení zkopíruje neinicializovanou hodnotu, ale druhé jej přepíše správnou hodnotou i .

Fisher-Yates však není nejrychlejším algoritmem pro generování permutace, protože Fisher-Yates je v podstatě sekvenční algoritmus a postupy „rozděl a panuj“ mohou dosáhnout stejného výsledku paralelně.

Generování v lexikografickém pořadí

Existuje mnoho způsobů, jak systematicky generovat všechny permutace dané sekvence. Jeden klasický, jednoduchý a flexibilní algoritmus je založen na nalezení další permutace v lexikografickém uspořádání , pokud existuje. Dokáže zpracovat opakované hodnoty, v takovém případě generuje každou odlišnou vícesetovou permutaci jednou. I pro běžné permutace je to mnohem efektivnější než generování hodnot pro Lehmerův kód v lexikografickém pořadí (případně pomocí systému faktoriálních čísel ) a jejich převod na permutace. Začíná seřazením sekvence v (slabě) rostoucím pořadí (což dává její lexikograficky minimální permutaci), a poté opakuje postup k další permutaci, dokud je nalezena. Metoda sahá až do Narayana Pandita v Indii 14. století a byla znovu objevena často.

Následující algoritmus generuje další permutaci lexikograficky po dané permutaci. Mění danou permutaci na místě.

1. Najděte největší index k tak, že a [ k ] < a [ k + 1] . Pokud žádný takový index neexistuje, je permutace poslední permutací.
2. Najděte největší index l větší než k tak, aby a [ k ] < a [ l ] .
3. Vyměňte hodnotu a [ k ] za hodnotu [ l ].
4. Obraťte posloupnost od a [ k + 1] až po konečný prvek a [ n ] včetně.

Například vzhledem k posloupnosti [1, 2, 3, 4] (která je v rostoucím pořadí) a vzhledem k tomu, že index je založen na nule , jsou kroky následující:

1. Index k = 2, protože 3 je umístěno na index, který splňuje podmínku největšího indexu, který je stále menší než a [ k + 1], což je 4.
2. Index l = 3, protože 4 je jediná hodnota v pořadí, která je větší než 3, aby byla splněna podmínka a [ k ] < a [ l ].
3. Hodnoty a [2] a a [3] jsou prohozeny, aby vytvořily novou sekvenci [1, 2, 4, 3].
4. Posloupnost po k -indexu a [2] ke konečnému prvku je obrácena. Protože za tímto indexem (3) leží pouze jedna hodnota, sekvence v tomto případě zůstane beze změny. Je tedy permutován lexikografický nástupce počátečního stavu: [1, 2, 4, 3].

Podle tohoto algoritmu bude další lexikografická permutace [1, 3, 2, 4] a 24. permutace bude [4, 3, 2, 1], přičemž v bodě a [ k ] < a [ k + 1] neexistuje, což naznačuje, že se jedná o poslední permutaci.

Tato metoda používá asi 3 srovnání a 1,5 swapu na jednu permutaci, amortizovanou v celé sekvenci, bez počátečního řazení.

Generování s minimálními změnami

Alternativa k výše uvedenému algoritmu, Steinhaus – Johnson – Trotterův algoritmus , generuje uspořádání na všech permutacích dané sekvence s vlastností, že jakékoli dvě po sobě jdoucí permutace ve svém výstupu se liší prohozením dvou sousedních hodnot. Toto uspořádání permutací bylo známé anglickým zvonařům 17. století, mezi nimiž byl znám jako „prosté změny“. Jednou výhodou této metody je, že malé množství změny z jedné permutace na druhou umožňuje, aby byla metoda implementována v konstantním čase na jednu permutaci. Totéž může také snadno generovat podmnožinu sudých permutací, opět v konstantním čase na permutaci, přeskočením každé další výstupní permutace.

Alternativou k Steinhaus – Johnson – Trotter je Heapův algoritmus , který v roce 1977 řekl Robert Sedgewick jako nejrychlejší algoritmus generování permutací v aplikacích.

Následující obrázek ukazuje výstup všech tří výše uvedených algoritmů pro generování všech permutací délky a šesti dalších algoritmů popsaných v literatuře. ${\ displaystyle n = 4}$

1. Lexikografické řazení;
2. Algoritmus Steinhaus – Johnson – Trotter ;
3. Halův algoritmus ;
4. Ehrlichův algoritmus transpozice hvězd: v každém kroku je první vstup permutace vyměněn za pozdější vstup;
5. Zaksův algoritmus obrácení prefixu: v každém kroku je obrácen prefix aktuální permutace, aby se získala další permutace;
6. Algoritmus Sawada-Williamse: každá permutace se liší od předchozí buď cyklickým posunem doleva o jednu pozici, nebo výměnou prvních dvou položek;
7. Corbettův algoritmus: každá permutace se liší od té předchozí cyklickým posunem levé předpony o jednu pozici;
8. Jednosměrné řazení: každý sloupec je cyklický posun ostatních sloupců;
9. Jednostopý šedý kód: každý sloupec je cyklickým posunem ostatních sloupců plus jakékoli dvě po sobě jdoucí permutace se liší pouze jednou nebo dvěma transpozicemi.

Meandrické permutace

Meandrické systémy vedou k meandrickým permutacím , speciální podmnožině alternativních permutací . Alternativní permutace množiny {1, 2, ..., 2 n } je cyklická permutace (bez pevných bodů) tak, že číslice ve formě cyklické notace střídají lichá a sudá celá čísla. Meandrické permutace jsou užitečné při analýze sekundární struktury RNA. Ne všechny alternativní permutace jsou meandrické. Modifikace Heapova algoritmu byla použita ke generování všech alternativních permutací řádu n (tj. O délce 2 n ) bez generování všech (2 n )! permutace. Generování těchto alternativních permutací je nutné před jejich analýzou, aby se zjistilo, zda jsou meandrické nebo ne.

Algoritmus je rekurzivní. Následující tabulka ukazuje krok v postupu. V předchozím kroku byly vygenerovány všechny alternativní permutace délky 5. Tři kopie každé z nich mají na pravém konci přidáno „6“ a poté je použita jiná transpozice zahrnující tento poslední záznam a předchozí záznam v rovnoměrné poloze (včetně identity; to znamená, že žádná transpozice).

Předchozí sady	Transpozice číslic	Alternativní permutace
1-2-3-4-5-6		1-2-3-4-5-6
	4, 6	1-2-3-6-5-4
	2, 6	1-6-3-4-5-2
1-2-5-4-3-6		1-2-5-4-3-6
	4, 6	1-2-5-6-3-4
	2, 6	1-6-5-4-3-2
1-4-3-2-5-6		1-4-3-2-5-6
	2, 6	1-4-3-6-5-2
	4, 6	1-6-3-2-5-4
1-4-5-2-3-6		1-4-5-2-3-6
	2, 6	1-4-5-6-3-2
	4, 6	1-6-5-2-3-4

Aplikace

Permutace se používají v prokládací komponentě algoritmů detekce a korekce chyb, jako jsou turbo kódy , například mobilní telekomunikační standard 3GPP Long Term Evolution tyto nápady používá (viz technická specifikace 3GPP 36.212). Takové aplikace vyvolávají otázku rychlého generování permutací splňujících určité žádoucí vlastnosti. Jedna z metod je založena na permutačních polynomech . Také jako základ pro optimální hašování v Unique Permutation Hashing.

Viz také

Poznámky

Reference

Bibliografie

• Bogart, Kenneth P. (1990), Introductory Combinatorics (2nd ed.), Harcourt Brace Jovanovich, ISBN 978-0-15-541576-8
• Bóna, Miklós (2004), Combinatorics of Permutations , Chapman Hall-CRC, ISBN 978-1-58488-434-7
• Bona, Miklos (2012), Combinatorics of Permutations (2. vyd.), CRC Press, ISBN 978-1-4398-5051-0
• Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, ISBN 978-0-13-602040-0
• Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms , Cambridge University Press, ISBN 978-0-521-45761-3
• Carmichael, Robert D. (1956) [1937], Úvod do teorie skupin konečného řádu , Dover, ISBN 978-0-486-60300-1
• Fraleigh, John B. (1976), první kurz abstraktní algebry (2. vydání), Reading: Addison-Wesley , ISBN 0-201-01984-1
• Gerstein, Larry J. (1987), Diskrétní matematika a algebraické struktury , WH Freeman and Co., ISBN 978-0-7167-1804-8
• Hall, Marshall, Jr. (1959), Theory of Groups , MacMillan
• Humphreys, JF (1996), Kurz teorie skupiny , Oxford University Press, ISBN 978-0-19-853459-4
• Knuth, Donald (1973), Třídění a hledání , Umění počítačového programování, 3 Tato kniha zmiňuje Lehmerův kód (bez použití tohoto jména) jako variantu C ₁ , ..., C _n inverzních tabulek ve cvičení 5.1.1–7 (str. 19) spolu s dalšími dvěma variantami.
• Knuth, Donald (2005), Generating All Tuples and Permutations , The Art of Computer Programming , 4 , Addison – Wesley, ISBN 978-0-201-85393-3 Fascicle 2, první tisk.
• McCoy, Neal H. (1968), Introduction to Modern Algebra, Revised Edition , Boston: Allyn and Bacon , LCCN  68015225
• Nering, Evar D. (1970), Lineární algebra a maticová teorie (2. vydání), New York: Wiley , LCCN  76091646
• Rotman, Joseph J. (2002), Advanced Modern Algebra , Prentice-Hall, ISBN 978-0-13-087868-7
• Stedman, Fabian (1677), Campanalogia , London Vydavatel je uveden jako „WS“, což může být William Smith, případně jednající jako agent Společnosti vysokoškolských mládeže , jíž je společnost „Dedicatory“ určena. V uvozovkách bylo původní dlouhé „S“ nahrazeno moderním krátkým „s“.
• Websterův sedmý nový vysokoškolský slovník , Springfield: G. & C. Merriam Company , 1969

Další čtení

• Biggs, Norman L. (2002), Discrete Mathematics (2. vyd.), Oxford University Press, ISBN 978-0-19-850717-8
• Foata, Dominique; Schutzenberger, Marcel-Paul (1970), Théorie Géométrique des Polynômes Eulériens , Lecture Notes in Mathematics, 138 , Berlin, Heidelberg: Springer-Verlag, ISBN 978-3-540-04927-2. Odkaz je na volně dostupnou přepisovanou (LaTeX'ed) a revidovanou verzi textu původně publikovaného Springer-Verlag.
• Knuth, Donald (1998), Sorting and Searching , The Art of Computer Programming, 3 (Second ed.), Addison – Wesley, ISBN 978-0-201-89685-5. Oddíl 5.1: Kombinatorické vlastnosti permutací, s. 11–72.
• Sedgewick, Robert (1977). „Metody generování permutace“. Výpočetní průzkumy ACM . 9 (2): 137–164. doi : 10,1145/356689,356692 . S2CID  12139332 .

externí odkazy

• "Permutace" , encyklopedie matematiky , EMS Press , 2001 [1994]