Narayana Algorithm For Next Lexicographic Permutation
This online calculator implements Narayana algorithm to generate the next permutation in lexicographic order
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 elements ordered such that , it will generate all permutations of the elements of the set in lexicographic order1.
You can read the description of the algorithm below the calculator.
Narayana Algorithm
- Find such a largest for which .
- Increase . To do this, find the largest for which . Then swap and .
- Write the sequence in reverse order.
The algorithm was invented by Indian mathematician Pandit Narayana in the 14th century.
-
Knuth, D. E. The Art of Computer Programming. — Addison-Wesley, 2005. — Vol. 4. — ISBN 0-201-85393-0 ↩
Comentários