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:



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 order1.

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

PLANETCALC, Narayana Algorithm For Next Lexicographic Permutation

Narayana Algorithm For Next Lexicographic Permutation

Comma-separated list of permutation elements
The file is very large. Browser slowdown may occur during loading and creation.

Narayana Algorithm

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

The algorithm was invented by Indian mathematician Pandit Narayana in the 14th century.

  1. Knuth, D. E. The Art of Computer Programming. — Addison-Wesley, 2005. — Vol. 4. — ISBN 0-201-85393-0 

URL copied to clipboard
PLANETCALC, Narayana Algorithm For Next Lexicographic Permutation