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

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

Этот онлайн калькулятор иллюстрирует работу нерекурсивного алгоритма Нарайаны для генерации перестановок в лексикографическом порядке. Вы вводите элементы начальной перестановки, разделенные запятыми, и количество итераций алгоритма (перестановка, полученная на предыдущей итерации, является начальной перестановкой следующей итерации). Данные по умолчанию - перестановка 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}\} в лексикографическом порядке1.

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

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

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

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

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

  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} в обратном порядке.

Алгоритм придуман индийским математиком Пандитом Нарайаной в XIV веке.

Ссылка скопирована в буфер обмена
PLANETCALC, Алгоритм Нарайаны

Комментарии