Онлайн калькулятор: Алгоритм Нарайаны

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

Этот онлайн-калькулятор реализует алгоритм Нарайаны для генерации следующей перестановки в лексикографическом порядке

Эта страница существует благодаря следующим персонам

	Timur Статья : Алгоритм Нарайаны - Автор Калькулятор : Алгоритм Нарайаны - Автор
A	Anton Статья : Алгоритм Нарайаны - Редактор

Создан: 2019-12-18 17:06:30, Последнее изменение: 2020-11-03 14:19:38

Этот онлайн калькулятор иллюстрирует работу нерекурсивного алгоритма Нарайаны для генерации перестановок в лексикографическом порядке. Вы вводите элементы начальной перестановки, разделенные запятыми, и количество итераций алгоритма (перестановка, полученная на предыдущей итерации, является начальной перестановкой следующей итерации). Данные по умолчанию - перестановка 1,2,3 и количество итераций 6 генерируют все возможные перестановки из трех элементов (три факториал) и возвращают к начальной перестановке.

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

Описание алгоритма можно прочитать под калькулятором.

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

Перестановка

Элементы перестановки, разделенные запятой

Количество итераций

Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

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

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