Module: Iterando sobre permutaciones


Problem

1 /4


Todas las permutaciones

Theory Click to read/hide

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.

Problem

Se le da un número natural n. Imprime todas las permutaciones de tamaño n en orden lexicográfico.

Entrada:
La primera línea contiene un número natural n (1 <= n <= 7).

Salida:
Imprime todas las permutaciones en orden ascendente en orden lexicográfico. Cada uno en una línea separada. Los números en la permutación deben estar separados por espacios.

Ejemplo:
 
Entrada Salida
3 1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1