Алгори́тм Нарайа́ны — нерекурсивный алгоритм, генерирующий по данной перестановке следующую за ней перестановку (в лексикографическом порядке). Придуман индийским математиком в XIV веке.
Если алгоритм Нарайаны применить в цикле к исходной последовательности из элементов , упорядоченных так, что , то он сгенерирует все перестановки элементов множества в лексикографическом порядке.
Другой особенностью алгоритма является то, что необходимо запоминать только один элемент перестановки.
Алгоритм Шаг 1: найти такой наибольший , для которого . Шаг 2: увеличить . Для этого надо найти наибольшее , для которого . Затем поменять местами и . Шаг 3: записать последовательность в обратном порядке.
Оценка сложности В случае перестановки, где элементы перемешаны случайным образом, сложность алгоритма практически не зависит от количества элементов. В приведённых реализациях производится в среднем 3 сравнения элементов перестановки и 2.17 обменов.
Наилучшим является случай, когда предпоследний элемент перестановки больше последнего, тогда производится 2 сравнения и 1 обмен. Худшим является случай, когда элементы перестановки отсортированы по убыванию, и, если длина перестановки равна n, то производится n+1 сравнений и n/2+1 обменов.
В целом сложность алгоритма можно оценить как O(n).
Литература
Категория:Алгоритмы Категория:Комбинаторика Категория:Комбинаторные алгоритмы