Tujuan
Anda diberi integer n
( n > 1
). Anda harus keluaran berapa banyak permutasi dari bilangan bulat 1
untuk n
ada yang mulai 1
, berakhir pada n
, dan tidak memiliki dua bilangan bulat berturut-turut yang berbeda dengan 1.
Atau, jika Anda mengambil grafik lengkap K_n
dan menghapus tepi jalan 1-2-3-...-n
Anda harus menghitung jalur Hamiltonian dari 1
ke n
dalam grafik yang tersisa.
Contoh-contoh akan digunakan f(n)
untuk fungsi yang menerima n
dan mengeluarkan jumlah permutasi yang valid, tetapi kiriman Anda bisa berupa fungsi atau program.
Contohnya
Sebab n = 6
, solusi yang mungkin adalah1-3-5-2-4-6
Namun, 1-3-5-2-6-4
ini bukan solusi yang valid karena tidak berakhir dengan 6
.
Bahkan, untuk n = 6
, hanya ada 2 solusi ( 1-4-2-5-3-6
yang lain).
Oleh karena itu f(6) = 2
.
Untuk n = 4
satu-satunya permutasi yang dimulai 1
dan diakhiri 4
adalah 1-2-3-4
dan 1-3-2-4
. Di keduanya 2
berdekatan dengan 3
, memberikan bilangan bulat berturut-turut yang berbeda dengan 1. Oleh karena itu f(4) = 0
.
Uji kasus
f(6) = 2
f(4) = 0
f(8) = 68
f(13) = 4462848
Kriteria menang
Ini adalah kode-golf, jawaban terpendek menang.
sumber
[2..n-1]
mengandung delta1
atau-1
, Anda juga harus memeriksa bahwa tidak ada permutasi yang dimulai2
atau diakhiri dengann-1
...Q_ser:=z + 2 z^6 + 10 z^7 + 68 z^8 + 500 z^9 + 4174 z^10 + 38774 z^11 + 397584z^12 + 4462848 z^13 + 54455754 z^14
saya menghabiskan beberapa waktu sekarang mencoba menggunakan rumus, tetapi saya tidak dapat membuat satu yang menghasilkan urutan. Luar biasa melihat eksponen z adalah input rumus dan hasilnya adalah faktor multiplikasi. Yang bagaimana dapat menyimpulkan rumus dari sana mungkin ada satu dengan jawaban terpendek dalam byteJawaban:
MATL , 16 byte
Cobalah online!
Untuk input yang melebihi
12
, kehabisan memori.Penjelasan
sumber
Mathematica, 58 byte, polinomial ( n ) waktu
Bagaimana itu bekerja
Daripada mengulangi permutasi dengan brute force, kami menggunakan prinsip inklusi-eksklusi untuk menghitungnya secara kombinatorial.
Misalkan S adalah himpunan semua permutasi [1,…, n] dengan σ 1 = 1, σ n = n , dan biarkan S i adalah himpunan permutasi σ ∈ S sedemikian rupa sehingga | σ i - σ i + 1 | = 1. Kemudian hitungan yang kita cari adalah
| S | - | S 1 ∪ ⋯ ∪ S n - 1 | = ∑ 2 ≤ k ≤ n + 1; 1 ≤ i 2 <⋯ < i k - 1 < n (−1) k - 2 | S i 2 ∩ ⋯ ∩ S i k - 1 |
Sekarang, | S i 2 ∩ ⋯ ∩ S i k - 1 | hanya tergantung pada k dan pada jumlah j run dari indeks berurutan di [ i 1 , i 2 ,…, i k - 1 , i k ] di mana untuk kenyamanan kami memperbaiki i 1 = 0 dan i k = n . Secara khusus,
| S i 2 ∩ ⋯ ∩ S i k - 1 | = 2 j - 2 ( n - k ) !, untuk 2 ≤ j ≤ k ≤ n ,
| S i 2 ∩ ⋯ ∩ S i k - 1 | = 1, untuk j = 1, k = n + 1.
Jumlah set indeks tersebut [ i 1 , i 2 ,…, i k - 1 , i k ] dengan j run adalah
( k - 1 C j - 1 ) ( n - k C j - 2 ), untuk 2 ≤ j ≤ k ≤ n ,
1, untuk j = 1, k = n + 1.
Hasilnya kemudian
(−1) n - 1 + ∑ 2 ≤ k ≤ n ∑ 2 ≤ j ≤ k (−1) k - 2 ( k - 1 C j - 1 ) ( n - k C j - 2 ) 2 j - 2 ( n - k )!
Jumlah batin lebih j dapat ditulis menggunakan hipergeometrik 2 F 1 fungsi :
(−1) n - 1 + ∑ 2 ≤ k ≤ n (−1) k ( k - 1) 2 F 1 (2 - k , k - n ; 2; 2) ( n - k )!
dimana kami menerapkan transformasi Pfaff yang memungkinkan kami menghilangkan kekuatan −1 menggunakan nilai absolut:
(−1) n - 1 + ∑ 2 ≤ k ≤ n (−1) n ( k - 1) 2 F 1 ( k , k - n ; 2; 2) ( n - k )!
= | −1 + ∑ 1 ≤ k ≤ n ( k - 1) 2 F 1 ( k , k - n ; 2; 2) ( n - k )! |.
Demo
sumber
Jelly ,
1716 byteTautan monadik.
Cobalah online!
Bagaimana?
sumber
IỊṀ
itu valid. Secara khusus, bagaimana jika-2
ada salah satu delta di sana misalnya? Anda dapat memperbaikinya denganIAỊṀ
untuk +1.x <= 1
.Japt ,
1918 byteUji secara online! Saya tidak akan merekomendasikan pengujian pada apa pun yang lebih besar dari
10
.Penjelasan
sumber
1
.n > 1
.05AB1E , 17 byte
Cobalah online!
sumber
¹1Š)˜
menghemat satu byte.Haskell,
7665 byteDisimpan 11 byte berkat @xnor.
Menggunakan hasil untuk
Q_rec
pada halaman 7 dari temuan @ ChristiaanWesterbeek, kita dapatkanSaya tidak mengerti bagaimana hasil mereka selanjutnya
ha
terkait dengan ini, tetapi setelah mempercepat (pertama dengan memoisasi, lihat versi sebelumnya, lalu seperti di bawah) saya mendapatkan nomor mereka.Meskipun hal di atas tidak apa-apa
n=20
, penting sekali contoh bagaimana tidak melakukan rekursi. Ini adalah versi yang lebih cepat (hanya untukn>=6
) yang juga hanya akan membutuhkan memori konstan - jika saja angkanya tidak terus meningkat ...Itu memberi
Tidak masalah juga untuk mendapatkan
f 5000
tetapi saya tidak ingin menempelkan hasilnya ...BTW, dimungkinkan untuk tidak menggunakan matematika mewah dan masih tidak menggunakan kekuatan kasar (ultra). Pertama, alih-alih melihat semua permutasi, lihatlah permutasi parsial dan hanya perluas ketika permutasi belum valid. Tidak ada gunanya untuk melihat semua permutasi yang dimulai dengan
1 6 5
. Kedua, beberapa permutasi parsial menyukai1 3 5 7
dan1 5 3 7
memiliki kelanjutan valid yang sama persis, jadi atasi semuanya. Dengan menggunakan ide-ide ini, saya bisa menghitung nilai hinggan=16
0,3 detik.sumber
f n=sum$zipWith((*).f)[n-5..][n-4,1,10-2*n,4,n-2]
.Python, 125 byte
sumber
Mathematica, 66 byte
Penjelasan
Function
dengan argumen pertama#
.sumber
Javascript (ES6),
100747260 byteDi bawah ini adalah versi sebelum penguasaan-golf @PeterTaylor
Berkat jawaban dari @ChristianSievers yang berhasil menyusun solusi Haskell dari makalah yang saya temukan setelah googling '0, 2, 10, 68, 500, 4174, 38774, 397584', ini adalah versi Javascript yang tidak permutasi juga.
Pemakaian
sumber
f(n)
kapann>1
, jadi tidak masalah untuk apa Anda kembalin=1
. Saya juga berpikirf(1)=1
itu benar.n<6?n==1|0:
untuk penghematan dua char selanjutnya.f=n=>n--<6?!n|0:f(n)*--n+4*f(n--)-2*f(n--)*--n+f(n)*++n+f(n)
Brachylog , 26 byte
Cobalah online!
Penjelasan
sumber
Python 3 ,
109107102 byteCobalah online!
Dihapus empat byte dengan tidak mencoba fungsi satu-baris (seperti yang disarankan oleh @shooqie) dan byte lain dengan mengganti
abs
dengan kuadrat. (Membutuhkan Python 3.5+)sumber
Python 2 , 136 byte
-10 byte terima kasih kepada @ovs.
Cobalah online!
sumber
Mathematica, 134 byte
test case n: 2 hingga 12
sumber
Python 2 , 105 byte
Cobalah online!
Ini didasarkan pada kertas Philippe Flajolet yang ditemukan oleh @Christiaan Westerbeek ; itu jauh lebih cepat dan dua byte lebih pendek dari solusi Python 3 saya yang menyebutkan kemungkinan permutasi. (Dalam Python 3,
reduce
telah dipindahkan kefunctools
.)Ada versi yang jauh lebih singkat menggunakan produk dot numpy, tetapi meluap cukup cepat dan membutuhkan numpy telah diimpor. Tapi untuk apa nilainya:
sumber