Una permutación de longitud n es una colección ordenada sin repeticiones de los números 1, 2, ..., n. Por ejemplo, [3, 1, 2] y [5, 4, 3, 2, 1] son permutaciones, pero [1, 2, 1, 3] y [1, 2, 4] no lo son.
Si la tarea se reduce al hecho de que es necesario iterar sobre todas las permutaciones de longitud n, entonces puede usar un mecanismo conveniente en C ++, que se llama "next_permutation".
Puede leer más sobre esto en documentación, pero el punto es que esta función cambia la matriz pasada a la permutación posterior en orden lexicográfico (que generalmente es claro y su nombre).
Para usar next_permutation, debe incluir la biblioteca de algoritmos (es decir, escriba #include <algorithm> al comienzo del programa)
Ejemplos:
vectorarr;
matriz = { 1, 2, 3 }; // la matriz es [1, 2, 3]
next_permutation(arr.begin(), arr.end()); // pasar todo el arreglo a la función
// la matriz ahora es [1, 3, 2]
matriz = { 2, 3, 1 }; // la matriz es [2, 3, 1]
next_permutation(arr.begin(), arr.end()); // pasar todo el arreglo a la función
// la matriz ahora es [3, 1, 2]
next_permutation(arr.begin() + 1, arr.begin() + 3); // es posible aplicar una función a una parte de una matriz, pero en la práctica esto rara vez es necesario
// la matriz ahora es [3, 2, 1]
En este caso, la función tiene un valor de retorno booleano que es verdadero si se generó la siguiente permutación y falso si no hubo ninguna (el caso en que se pasa a la función la máxima permutación en orden lexicográfico).
Esto hace posible usar la función en un bucle, lo que nos permitirá iterar sobre todas las permutaciones a la vez. Debido a la indexación 0, en la práctica suele ser más conveniente trabajar con una permutación de números de 0 a n - 1, aunque una permutación contiene formalmente números de 1 a n. Pero, afortunadamente, esto no conduce a superposiciones adicionales en el código, porque la función next_permutation está adaptada a permutaciones indexadas en 0 (e incluso elementos duplicados en una matriz, pero puede encontrar más por su cuenta).
En general, el código para iterar sobre todas las permutaciones tiene este aspecto:
interno; // tamaño de la permutación
vectorperm(n); // perm es la abreviatura de "permutación", es decir "permutación"
para (int i = 0; i < n; i++)
permanente[i] = i; // inicializa la permutación inicial 0, 1, ..., n - 1
hacer {
// dentro del bucle procesamos la permutación actual
} while (next_permutation(perm.begin(), perm.end())); // si no hay permutación siguiente, finaliza el bucle
Este código se ejecuta en O(n! * f(n)), donde f(n) es el tiempo que le lleva procesar una permutación en particular.