Permutaciones

¿Quién de vosotros no ha tenido alguna vez que generar permutaciones o se ha visto tentado a ello para dar solución directa a algún problema de programación? Yo, la verdad, más de una. Puede resultar especialmente útil en problemas resueltos típicamente mediante el esquema algorítimico de "Vuelta Atrás" donde hay que explorar un espacio de estados. Si cada estado solución fuese una de entre n! permutaciones, siendo n el número de elementos a combinar, generar ordenadamente todas las permutaciones, pero de forma "Voraz", sería lo ideal. Aquí tenéis un algoritmo para hacerlo:

Sea la permutación P = x(1), x(2), ..., x(n)

1) Se busca de derecha a izquierda el primer número x(i) que se menor que el que le sigue [x(i) < x(i+1)].

2) Se busca de derecha a izquierda el primer número x(j) que sea mayor que x(i) [x(j) > x(i)].

3) Se intercambian ambos números.

4) Se invierten los números que siguen a la posición i.

Por ejemplo, si se están generando las permutaciones de 7:
Sea P = 5, 6, 3, 7, 4, 2, 1

1.- x(i) = 3 (3<7)
2.- x(j) = 4 (4>3)
3.- 5, 6, 4, 7, 3, 2, 1
4.- 5, 6, 4, 1, 2, 3, 7 (que sería la siguiente permutación a P)

Bibliografía: "Metodología de la Programación". Eduardo Alcalde - Miguel García. Segunda edición. Ed. McGrawHill. Pag 186.