Raiz quadrada de permutação

21

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 3tem 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
lirtosiast
fonte
Eu estaria correto ao dizer que, para uma permutação ter uma raiz quadrada, se ela contiver n ciclos de comprimento m, então n é par ou m é ímpar?
Neil
@ Neil Yes. Caso contrário, a permutação pode ser representada como um número ímpar de swaps.
precisa saber é o seguinte
Ah, sim, é uma maneira muito melhor de colocar isso.
Neil
11
relacionado
Liam

Respostas:

4

Perl, 124 122 bytes

Inclui +3 para -alp

Execute com a permutação baseada em 1 no STDIN:

rootperm.pl <<< "8 3 9 1 5 4 10 13 2 12 6 11 7"

rootperm.pl:

map{//;@{$G[-1]^$_|$0{$_}}{0,@G}=(@G=map{($n+=$s{$_=$F[$_-1]}++)?():$_}(0+$',0+$_)x@F)x2,%s=$n=0for@F}@F;$_="@0{1..@F}"

A complexidade é O (n ^ 3)

Ton Hospel
fonte
Por que a complexidade O (n ^ 3)?
CalculatorFeline
@CatsAreFluffy Porque é um programa estúpido :-). Ele considera cada par de elementos (mesmo se já tratado, O (n ^ 2)) e fecha seus ciclos juntos (nem mesmo sabendo quando parar, O (n)) e depois verifica se esse seria um ciclo adequado para uma raiz quadrada . No programa, você pode ver os 3 loops aninhados como 2 mapas e um
Ton Hospel 7/16/16
Oh. Faz sentido.
CalculatorFeline
2

Mathematica, 165 167 bytes

Uma função sem nome.

PermutationList[Cycles@Join[Riffle@@@#~(s=Select)~EvenQ@*(l=Length)~SortBy~l~Partition~2,#[[Mod[(#+1)/2Range@#,#,1]&@l@#]]&/@#~s~OddQ@*l]&@@PermutationCycles@#,l@#]&

Semi-sem golfe:

PermutationList[
    Cycles@Join[
        Riffle@@@Partition[SortBy[Select[#,EvenQ@*Length],Length], 2],
        #[[Mod[(Length@#+1)/2Range@Length@#,Length@#,1]]]& /@ Select[#,OddQ@*Length]
    ]& @@ PermutationCycles @ #,
    Max@#
]&
feersum
fonte
Com que mágica isso funciona?
CalculatorFeline
11
@CatsAreFluffy Se eu entendi o código semi-não-corretamente, ele divide a permutação em ciclos, agrupa-os por comprimento e, para os mais estranhos, os eleva à potência (comprimento + 1) / 2, enquanto para os pares emparelha-os e junta-os. (Se os mesmo ciclos não pode ser emparelhado a partição não tem raiz quadrada.)
Neil
0

Prolog - 69 caracteres

p([],_,[]). p([H|T],B,[I|U]):-p(T,B,U),nth1(H,B,I). f(X,Y):-p(Y,Y,X).

Explicação:

permutate([], _, []).                 % An empty permutation is empty
permutate([X|Xs], List, [Y|Ys]) :-    % To permutate List
  permutate(Xs, List, Ys),            % Apply the rest of the permutation
  nth1(X, List, Y).                   % Y is the Xth element of List

root(Permutation, Root) :-            % The root of Permutation
  permutate(Root, Root, Permutation). % Applied to itself, is Permutation
AtnNn
fonte
3
Eu imagino que isso leva tempo exponencial.
precisa saber é
Oh, certo. Vou ter que consertar isso.
AtnNn