Online calculator: Narayana Algorithm For Next Lexicographic Permutation

Narayana Algorithm For Next Lexicographic Permutation

This online calculator implements Narayana algorithm to generate the next permutation in lexicographic order

This page exists due to the efforts of the following people:

Timur

Article : Narayana Algorithm For Next Lexicographic Permutation - Author, Translator ru - en
Calculator : Narayana Algorithm For Next Lexicographic Permutation - Author, Translator ru - en

Created: 2023-11-14 15:34:48, Last updated: 2023-11-15 08:07:00

This online calculator illustrates the operation of Narayana's non-recursive algorithm for generating permutations in lexicographic order. You enter the elements of the initial permutation, separated by commas, and the number of iterations of the algorithm (the permutation obtained in the previous iteration is the initial permutation of the next iteration). The default data - permutation 1,2,3 and number of iterations 6 generates all possible permutations of three elements (three factorial) and returns to the initial permutation.

This is illustrated by the fact that if Narayana algorithm is applied in a loop to an initial sequence of $n$ elements $a_{1},a_{2},... ,a_{n}$ ordered such that $a_{1}\leqslant a_{2}\leqslant ...\leqslant a_{n}$ , it will generate all permutations of the elements of the set $\{a_{1},a_{2},...,a_{n}\}$ in lexicographic order¹.

You can read the description of the algorithm below the calculator.

Narayana Algorithm For Next Lexicographic Permutation

List of elements

Comma-separated list of permutation elements

Number of iterations

The file is very large. Browser slowdown may occur during loading and creation.

Narayana Algorithm

Find such a largest $j$ for which $a_{j}<a_{j+1}$ .
Increase $a_{j}$ . To do this, find the largest $i>j$ for which $a_{i}>a_{j}$ . Then swap $a_{j}$ and $a_{i}$ .
Write the sequence $a_{j+1},...,a_{n}$ in reverse order.