Em matemática, uma permutação σ da ordem n é uma função bijetiva dos números inteiros 1 ... n para si mesma. Esta lista:
2 1 4 3
representa a permutação σ tal que σ (1) = 2, σ (2) = 1, σ (3) = 4 e σ (4) = 3.
Uma raiz quadrada de uma permutação σ é uma permutação que, quando aplicada a si mesma, fornece σ . Por exemplo, 2 1 4 3
tem a raiz quadrada τ = 3 4 2 1
.
k 1 2 3 4
τ(k) 3 4 2 1
τ(τ(k)) 2 1 4 3
porque τ ( τ (k)) = σ (k) para todos os 1≤k≤n.
Entrada
Uma lista de n > 0 números inteiros, todos entre 1 e n , inclusive, representando uma permutação. A permutação sempre terá uma raiz quadrada.
Você pode usar uma lista de 0 ... n-1 , desde que sua entrada e saída sejam consistentes.
Saída
A raiz quadrada da permutação, também como uma matriz.
Restrições
Seu algoritmo deve ser executado no tempo polinomial em n . Isso significa que você não pode simplesmente passar por todos os n ! permutações de ordem n .
Quaisquer builtins são permitidos.
Casos de teste:
Observe que muitas entradas têm várias saídas possíveis.
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
fonte
Respostas:
Perl,
124122 bytesInclui +3 para
-alp
Execute com a permutação baseada em 1 no STDIN:
rootperm.pl
:A complexidade é O (n ^ 3)
fonte
Mathematica, 165
167bytesUma função sem nome.
Semi-sem golfe:
fonte
Prolog - 69 caracteres
Explicação:
fonte