Алгоритм Нарайаны

Алгори́тм Нарайа́ны — нерекурсивный алгоритм, генерирующий по данной перестановке следующую за ней перестановку (в лексикографическом порядке). Придуман индийским математиком Пандитом Нарайаной в XIV веке.

Если алгоритм Нарайаны применить в цикле к исходной последовательности из [math]\displaystyle{ n }[/math] элементов [math]\displaystyle{ a_{1},a_{2},...,a_{n} }[/math], упорядоченных так, что [math]\displaystyle{ a_{1} \leqslant a_{2} \leqslant ... \leqslant a_{n} }[/math], то он сгенерирует все перестановки элементов множества [math]\displaystyle{ \{a_{1},a_{2},...,a_{n}\} }[/math] в лексикографическом порядке.

Другой особенностью алгоритма является то, что необходимо запоминать только один элемент перестановки.

Алгоритм

• Шаг 1: найти такой наибольший [math]\displaystyle{ j }[/math], для которого [math]\displaystyle{ a_{j} \lt a_{j+1} }[/math].
• Шаг 2: увеличить [math]\displaystyle{ a_{j} }[/math]. Для этого надо найти наибольшее [math]\displaystyle{ l\gt j }[/math], для которого [math]\displaystyle{ a_{l} \gt a_{j} }[/math]. Затем поменять местами [math]\displaystyle{ a_{j} }[/math] и [math]\displaystyle{ a_{l} }[/math].
• Шаг 3: записать последовательность [math]\displaystyle{ a_{j+1},...,a_{n} }[/math] в обратном порядке.

Оценка сложности

В случае перестановки, где элементы перемешаны случайным образом, сложность алгоритма практически не зависит от количества элементов. В приведённых реализациях производится в среднем 3 сравнения элементов перестановки и 2.17 обменов.

Наилучшим является случай, когда предпоследний элемент перестановки больше последнего, тогда производится 2 сравнения и 1 обмен. Худшим является случай, когда элементы перестановки отсортированы по убыванию, и, если длина перестановки равна n, то производится n+1 сравнений и n/2+1 обменов.

В целом сложность алгоритма можно оценить как O(n).

Литература

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