Root Permutasi Square

21

Dalam matematika, permutasi σ dari urutan n adalah fungsi bijektif dari bilangan bulat 1 ... n ke dirinya sendiri. Daftar ini:

2 1 4 3

mewakili permutasi σ sedemikian rupa sehingga σ (1) = 2, σ (2) = 1, σ (3) = 4, dan σ (4) = 3.

Akar kuadrat dari permutasi σ adalah permutasi yang, ketika diterapkan pada dirinya sendiri, menghasilkan σ . Misalnya, 2 1 4 3memiliki akar kuadrat τ = 3 4 2 1.

k           1 2 3 4
τ(k)        3 4 2 1
τ(τ(k))     2 1 4 3

karena τ ( τ (k)) = σ (k) untuk semua 1≤k≤n.

Memasukkan

Daftar n > 0 integer, semuanya antara 1 dan n inklusif, mewakili permutasi. Permutasi akan selalu memiliki akar kuadrat.

Anda dapat menggunakan daftar 0 ... n-1 alih - alih selama input dan output Anda konsisten.

Keluaran

Akar kuadrat permutasi, juga sebagai array.

Batasan

Algoritme Anda harus dijalankan dalam waktu polinomial dalam n . Itu berarti Anda tidak bisa begitu saja melewati semua n ! permutasi pesanan n .

Semua bawaan diizinkan.

Kasus uji:

Perhatikan bahwa banyak input memiliki beberapa kemungkinan keluaran.

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
sumber
Apakah saya benar mengatakan bahwa permutasi memiliki akar kuadrat maka jika mengandung n siklus panjang m maka n adalah genap atau m aneh?
Neil
@Neil Ya. Kalau tidak permutasi dapat direpresentasikan sebagai jumlah swap yang ganjil.
jimmy23013
Ah ya itu cara yang lebih baik untuk menggambarkannya.
Neil
1
terkait
Liam

Jawaban:

4

Perl, 124 122 byte

Termasuk +3 untuk -alp

Jalankan dengan permutasi 1 berbasis pada 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}"

Kompleksitas adalah O (n ^ 3)

Ton Hospel
sumber
Mengapa kompleksitas O (n ^ 3)?
CalculatorFeline
@CatsAreFluffy Karena ini adalah program bodoh :-). Ini mempertimbangkan setiap pasangan elemen (bahkan jika sudah ditangani, O (n ^ 2)) dan ritsleting siklus mereka bersama-sama (bahkan tidak tahu kapan harus berhenti, O (n)) kemudian memeriksa apakah itu akan menjadi siklus yang tepat untuk akar kuadrat . Dalam program ini Anda dapat melihat 3 loop bersarang sebagai 2 peta dan untuk
Ton Hospel
Oh Masuk akal.
CalculatorFeline
2

Mathematica, 165 167 byte

Fungsi yang tidak disebutkan namanya.

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

Semi-ungolfed:

PermutationList[
    Cycles@Join[
        Riffle@@@Partition[SortBy[Select[#,EvenQ@*Length],Length], 2],
        #[[Mod[(Length@#+1)/2Range@Length@#,Length@#,1]]]& /@ Select[#,OddQ@*Length]
    ]& @@ PermutationCycles @ #,
    Max@#
]&
feersum
sumber
Dengan sihir apa ini bekerja?
CalculatorFeline
1
@CatsAreFluffy jika saya memahami kode semi-ungolfed dengan benar, itu membagi permutasi menjadi siklus, mengelompokkan mereka dengan panjang, kemudian untuk yang aneh itu mengangkat mereka ke kekuatan (panjang + 1) / 2 sedangkan untuk yang genap itu pasangkan dan riffles bersama. (Jika siklus genap tidak dapat dipasangkan maka partisi tersebut tidak memiliki akar kuadrat.)
Neil
0

Prolog - 69 karakter

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

Penjelasan:

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
sumber
3
Saya akan membayangkan ini membutuhkan waktu yang eksponensial.
feersum
Oh benar Saya harus memperbaikinya.
AtnNn