Algoritmus Narayana

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 25. září 2018; kontroly vyžadují 2 úpravy .

Narayanův algoritmus je nerekurzivní algoritmus , který pro danou permutaci generuje permutaci, která po ní následuje (v lexikografickém pořadí ). Vynalezen indickým matematikem Panditem Narayanou ve 14. století .

Pokud je Narayanův algoritmus aplikován ve smyčce na počáteční sekvenci prvků uspořádaných tak, že , vygeneruje všechny permutace prvků sady v lexikografickém pořadí. $n$ ${\displaystyle a_{1},a_{2},...,a_{n))$ ${\displaystyle a_{1}\leqslant a_{2}\leqslant ...\leqslant a_{n))$ $\{a_{1},a_{2},...,a_{n}\}$

Dalším rysem algoritmu je, že je nutné si pamatovat pouze jeden prvek permutace.

Algoritmus

Krok 1: najděte takové maximum, pro které . $j$ $a_{j}<a_{j+1}$
Krok 2: Zvětšení . Chcete-li to provést, musíte najít největší, pro které . Poté vyměňte a . $aj}$ $l>j$ ${\displaystyle a_{l}>a_{j))$ $aj}$ ${\displaystyle a_{l))$
Krok 3: Napište sekvenci v opačném pořadí. ${\displaystyle a_{j+1},...,a_{n))$

Hodnocení obtížnosti

V případě permutace, kde jsou prvky náhodně zamíchány, je složitost algoritmu prakticky nezávislá na počtu prvků. V daných implementacích jsou provedena průměrně 3 porovnání permutačních prvků a 2,17 výměn.

Nejlepší případ je, když je předposlední prvek permutace větší než poslední, pak se provedou 2 srovnání a 1 výměna. Nejhorší případ je, když jsou prvky permutace seřazeny sestupně, a pokud je délka permutace n, pak se provede n+1 porovnání a n/2+1 výměn.

Obecně lze složitost algoritmu odhadnout jako O(n).

Literatura

Knuth, D.E. The Art of Computer Programming. - Addison-Wesley, 2005. - Sv. 4. - ISBN 0-201-85393-0 .