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 3
memiliki 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
sumber
Jawaban:
Perl,
124122 byteTermasuk +3 untuk
-alp
Jalankan dengan permutasi 1 berbasis pada STDIN:
rootperm.pl
:Kompleksitas adalah O (n ^ 3)
sumber
Mathematica, 165
167byteFungsi yang tidak disebutkan namanya.
Semi-ungolfed:
sumber
Prolog - 69 karakter
Penjelasan:
sumber