Generar todas las permutaciones de n elementos distintos cuesta como mínimo…
Opciones
- O(n), porque cada elemento se visita una vez
- O(n²), porque se compara cada pareja
- O(n!) salidas, y O(n · n!) para escribirlas (Opción correcta)
- O(2ⁿ), porque cada elemento está o no está
Respuesta
O(n!) salidas, O(n · n!) para escribirlas
Por qué
Hay n! ordenaciones (3 elementos: 6; 10 elementos: 3.628.800), y cada permutación tiene n elementos que escribir.
Estos problemas se resuelven con backtracking: elige un elemento, recurre sobre el resto, y luego deshaz la elección y prueba el siguiente.
Para comparar, el número de subconjuntos es 2ⁿ.
Recuerda
Permutaciones = n!, subconjuntos = 2ⁿ.