En matemáticas, una permutación σ de orden n es una función biyectiva de los enteros 1 ... n a sí misma. Esta lista:
2 1 4 3
representa la permutación σ tal que σ (1) = 2, σ (2) = 1, σ (3) = 4 y σ (4) = 3.
Una raíz cuadrada de una permutación σ es una permutación que, cuando se aplica a sí misma, da σ . Por ejemplo, 2 1 4 3
tiene la raíz cuadrada τ = 3 4 2 1
.
k 1 2 3 4
τ(k) 3 4 2 1
τ(τ(k)) 2 1 4 3
porque τ ( τ (k)) = σ (k) para todos los 1≤k≤n.
Entrada
Una lista de n > 0 enteros, todos entre 1 y n inclusive, que representan una permutación. La permutación siempre tendrá una raíz cuadrada.
En su lugar, puede usar una lista de 0 ... n-1 siempre que su entrada y salida sean consistentes.
Salida
La raíz cuadrada de la permutación, también como una matriz.
Restricciones
Su algoritmo debe ejecutarse en tiempo polinómico en n . ¡Eso significa que no puedes simplemente recorrer todo n ! permutaciones de orden n .
Se permite cualquier construcción.
Casos de prueba:
Tenga en cuenta que muchas entradas tienen múltiples salidas posibles.
2 1 4 3
3 4 2 1
1
1
3 1 2
2 3 1
8 3 9 1 5 4 10 13 2 12 6 11 7
12 9 2 10 5 7 4 11 3 1 13 8 6
13 7 12 8 10 2 3 11 1 4 5 6 9
9 8 5 2 12 4 11 7 13 6 3 10 1
fuente
Respuestas:
Perl,
124122 bytesIncluye +3 para
-alp
Ejecute con la permutación basada en 1 en STDIN:
rootperm.pl
:La complejidad es O (n ^ 3)
fuente
Mathematica, 165
167bytesUna función sin nombre.
Semi-no-golfista:
fuente
Prolog - 69 caracteres
Explicación:
fuente