Algoritmo de Narayana

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 25 de septiembre de 2018; las comprobaciones requieren 2 ediciones .

El algoritmo de Narayana es  un algoritmo no recursivo que genera, para una permutación dada, la permutación que le sigue (en orden lexicográfico ). Inventado por el matemático indio Pandit Narayana en el siglo XIV .

Si el algoritmo de Narayana se aplica en bucle a la secuencia inicial de elementos ordenados de modo que , generará todas las permutaciones de los elementos del conjunto en orden lexicográfico.

Otra característica del algoritmo es que es necesario recordar solo un elemento de la permutación.

Algoritmo

Grado de dificultad

En el caso de una permutación, donde los elementos se barajan aleatoriamente , la complejidad del algoritmo es prácticamente independiente del número de elementos. En las implementaciones dadas , se realizan en promedio 3 comparaciones de elementos de permutación y 2,17 intercambios.

El mejor caso es cuando el penúltimo elemento de la permutación es mayor que el último, entonces se hacen 2 comparaciones y 1 intercambio. El peor caso es cuando los elementos de la permutación se clasifican en orden descendente, y si la longitud de la permutación es n, entonces se realizan n+1 comparaciones y n/2+1 intercambios.

En general, la complejidad del algoritmo se puede estimar como O(n).

Literatura