Difícil · recursión
Todas las permutaciones
Una permutación empieza con una elección: ¿qué número va primero? Fíjalo y lo que queda es el mismo problema un tamaño más pequeño. La recursión escribe esa frase literalmente: elegir, delegar, des-elegir.
En una fraseRecursión sobre posiciones: para cada valor v sin usar, ponlo, márcalo, recursión para la siguiente posición y desmárcalo. Probar los valores en orden creciente da el orden lexicográfico gratis.
El problema
Entrada: Un entero n (1 ≤ n ≤ 6).
Salida: Todas las n! permutaciones de 1..n, una por línea, valores separados por un espacio, en orden lexicográfico.
Ejemplos:
| Entrada | Salida |
|---|---|
3 | 1 2 3 |
n ≤ 6 porque 7! = 5040 líneas y 10! = 3,6 millones: el crecimiento factorial es toda la lección. La profundidad de la recursión es solo n; la explosión está en el número de ramas.
Tu solución
Entrada personalizada para «Ejecutar mi entrada»
La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.
¿Atascado? Pistas
Pista 1 — Escribe primero el caso base
Cuando pos == n el array perm está lleno: escríbelo con espacios simples y un salto de línea, y return. Toda recursión necesita un caso mínimo que detenga el descenso — escríbelo antes del bucle, o la función no tiene donde apoyarse.
Pista 2 — El bucle ES la ramificación
En la posición pos, recorre value de 1 a n. Salta los valores ya marcados en used. Si no: perm[pos] = value; used[value] = 1; generate(pos + 1); — y después, el paso que los principiantes olvidan: used[value] = 0; para devolver el valor. Probar los valores en orden creciente regala el orden lexicográfico.
Pista 3 — Confía en la recursión
Tras colocar un valor en pos, la llamada generate(pos + 1) debe producir todas las completaciones del prefijo actual, en orden, y devolver. No lo sigas a mano más de un nivel: la prueba es estructural: es exactamente el mismo problema, un tamaño más pequeño.
Solución (¡inténtalo primero!)
#include <iostream>
using namespace std;
int n;
int used[10];
int perm[10];
void generate(int pos) {
if (pos == n) {
for (int i = 0; i < n; i++) {
cout << perm[i];
if (i < n - 1) cout << " ";
}
cout << endl;
return;
}
for (int value = 1; value <= n; value++) {
if (used[value]) continue;
used[value] = 1;
perm[pos] = value;
generate(pos + 1);
used[value] = 0;
}
}
int main() {
cin >> n;
generate(0);
return 0;
}Acabas de escribir tu primer backtracking: elegir, recursión, des-elegir. El mismo esqueleto resuelve subconjuntos, N-reinas, Sudoku y laberintos — solo cambia el cuerpo del bucle. Para ver la recursión desde su otro lado (la pila de llamadas, no el árbol de búsqueda), sube a las Torres de Hanói.
Análisis profundo
Por qué funciona
El espacio de búsqueda es un árbol: la profundidad es la posición, las ramas son los valores sin usar. El backtracking recorre ese árbol en DFS lexicográfico, y el paso de desmarcar es el que permite que un valor reaparezca en otra rama — sin él, cada valor se usaría una sola vez en toda la ejecución.
El coste
O(n! × n) de tiempo — n! líneas, n de trabajo para escribir cada una — y O(n) de espacio para la pila de recursión y los arrays. Con n = 10 ya son 36 millones de líneas: el crecimiento factorial adelanta a cualquier optimización.
Dónde falla
- Olvidar
used[value] = 0;después de la llamada recursiva. Con n = 2 sales una línea en vez de dos; con n = 6, unas pocas en vez de 720 — y la causa es una sola línea ausente. - Escribir dentro del bucle en vez de en
pos == n. Emitirías cada prefijo parcial y el número de líneas dejaría de cuadrar con n!.
Siguiente paso
Mismo esqueleto, otras cargas: subconjuntos, N-reinas, laberintos. Y la vista de pila de llamadas de la recursión protagoniza Torres de Hanói.
Dos cosas para recordar
- Backtracking = elegir, recursión, des-elegir; lo de des-elegir no es opcional.
- Recorre los valores en orden creciente y el lexicográfico sale gratis.
🐞 Esta versión falla: ábrela y pruébala
Nunca devuelve el valor: falta used[value] = 0
#include <iostream>
using namespace std;
int n;
int used[10];
int perm[10];
void generate(int pos) {
if (pos == n) {
for (int i = 0; i < n; i++) {
cout << perm[i];
if (i < n - 1) cout << " ";
}
cout << endl;
return;
}
for (int value = 1; value <= n; value++) {
if (used[value]) continue;
used[value] = 1;
perm[pos] = value;
generate(pos + 1);
}
}
int main() {
cin >> n;
generate(0);
return 0;
}