Narayana algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 25. september 2018; checks kræver 2 redigeringer .

Narayanas algoritme er en ikke- rekursiv algoritme , der for en given permutation genererer den permutation, der følger efter den (i leksikografisk rækkefølge ). Opfundet af den indiske matematiker Pandit Narayana i det 14. århundrede .

Hvis Narayanas algoritme anvendes i en løkke til den indledende sekvens af elementer ordnet således, at , så vil den generere alle permutationer af elementerne i sættet i leksikografisk rækkefølge. $n$ ${\displaystyle a_{1},a_{2},...,a_{n))$ ${\displaystyle a_{1}\leqslant a_{2}\leqslant ...\leqslant a_{n))$ $\{a_{1},a_{2},...,a_{n}\}$

Et andet træk ved algoritmen er, at det kun er nødvendigt at huske ét element i permutationen.

Algoritme

Trin 1: find et sådant maksimum for hvilket . $j$ $a_{j}<a_{j+1}$
Trin 2: Forstør . For at gøre dette skal du finde den største , som . Skift derefter og . $a_{j}$ $l>j$ ${\displaystyle a_{l}>a_{j))$ $a_{j}$ ${\displaystyle a_{l))$
Trin 3: Skriv rækkefølgen i omvendt rækkefølge. ${\displaystyle a_{j+1},...,a_{n))$

Sværhedsgrad

I tilfælde af en permutation, hvor elementerne blandes tilfældigt , er kompleksiteten af algoritmen praktisk talt uafhængig af antallet af elementer. I de givne implementeringer foretages der i gennemsnit 3 sammenligninger af permutationselementer og 2,17 udvekslinger.

Det bedste tilfælde er, når det næstsidste element i permutationen er større end det sidste, så laves 2 sammenligninger og 1 udveksling. Det værste tilfælde er, når elementerne i permutationen er sorteret i faldende rækkefølge, og hvis længden af permutationen er n, så foretages n+1 sammenligninger og n/2+1 udvekslinger.

Generelt kan kompleksiteten af algoritmen estimeres som O(n).

Litteratur

Knuth, D.E. Kunsten at programmere computer. - Addison-Wesley, 2005. - Vol. 4. - ISBN 0-201-85393-0 .