Русская Википедия:Алгоритм Нарайаны

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

Алгоритм

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

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

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

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

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

Литература

• Шаблон:Книга