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

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

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

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

Алгоритм

Шаг 1: найти такой наибольший $j$ , для которого $a_{j}<a_{j+1}$ .
Шаг 2: увеличить $a_{j}$ . Для этого надо найти наибольшее $l>j$ , для которого $a_{l}>a_{j}$ . Затем поменять местами $a_{j}$ и $a_{l}$ .
Шаг 3: записать последовательность $a_{j+1},...,a_{n}$ в обратном порядке.

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

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

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

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