Menghitung dari 1 hingga n tanpa angka berurutan

19

Tujuan

Anda diberi integer n( n > 1). Anda harus keluaran berapa banyak permutasi dari bilangan bulat 1untuk nada 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_ndan menghapus tepi jalan 1-2-3-...-nAnda harus menghitung jalur Hamiltonian dari 1ke ndalam grafik yang tersisa.

Contoh-contoh akan digunakan f(n)untuk fungsi yang menerima ndan 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-4ini bukan solusi yang valid karena tidak berakhir dengan 6.

Bahkan, untuk n = 6, hanya ada 2 solusi ( 1-4-2-5-3-6yang lain).

Oleh karena itu f(6) = 2.


Untuk n = 4satu-satunya permutasi yang dimulai 1dan diakhiri 4adalah 1-2-3-4dan 1-3-2-4. Di keduanya 2berdekatan 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.

Philippe
sumber
7
Anda tahu, anak-anak, Anda tidak dapat hanya memeriksa berapa banyak permutasi yang [2..n-1]mengandung delta 1atau -1, Anda juga harus memeriksa bahwa tidak ada permutasi yang dimulai 2atau diakhiri dengan n-1...
ETHproduksi
1
Apakah daftar harus dimulai dengan 1 dan diakhiri dengan nomor?
Okx
3
Mungkin OP berarti "berdekatan" bukan "berturut-turut"?
Stilez
6
Anehnya urutannya ada di sini: algo.inria.fr/libraries/autocomb/graphs99.ps di mana pada halaman 6 ditulis, 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^14saya 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 byte
Christiaan Westerbeek
1
@ChristiaanWesterbeek yang disebut fungsi menghasilkan untuk urutan. Ada banyak urutan dengan fungsi pembangkit yang memiliki bentuk tertutup yang lebih bagus daripada urutan itu sendiri, ini adalah hal yang keren!
Carmeister

Jawaban:

6

MATL , 16 byte

qtq:Y@0&Yc!d|qAs

Cobalah online!

Untuk input yang melebihi 12, kehabisan memori.

Penjelasan

q      % Implicitly input n. Push n-1
tq     % Duplicate and subtract 1: pushes n-2
:      % Range [1 2 ... n-2]
Y@     % Matrix with all permutations, each in a row
0      % Push 0
&Yc    % Append n-1 and predend 0 to each row
!      % Tranpose
d      % Consecutive differences along each column
|      % Absolute value
q      % Subtract 1
A      % All: true if all values in each column are non-zero
s      % Sum. Implicitly display
Luis Mendo
sumber
1
Bekerja dengan baik, bagus :)
Philippe
1
Meskipun ada beberapa kemajuan yang sangat bagus dalam masalah ini, solusi Anda masih terpendek. Ini juga lebih cepat daripada yang Jelly. Selamat!
Philippe
19

Mathematica, 58 byte, polinomial ( n ) waktu

Abs[Sum[(k-1)Hypergeometric2F1[k,k-#,2,2](#-k)!,{k,#}]-1]&

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 ≤ kn + 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 ≤ jkn ,
| 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 ≤ jkn ,
1, untuk j = 1, k = n + 1.

Hasilnya kemudian

(−1) n - 1 + ∑ 2 ≤ kn2 ≤ jk (−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 ≤ kn (−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 ≤ kn (−1) n ( k - 1) 2 F 1 ( k , k - n ; 2; 2) ( n - k )!
= | −1 + ∑ 1 ≤ kn ( k - 1) 2 F 1 ( k , k - n ; 2; 2) ( n - k )! |.

Demo

In[1]:= Table[Abs[Sum[(k-1)Hypergeometric2F1[k,k-#,2,2](#-k)!,{k,#}]-1]&[n],{n,50}]

Out[1]= {1, 0, 0, 0, 0, 2, 10, 68, 500, 4174, 38774, 397584, 4462848, 

>    54455754, 717909202, 10171232060, 154142811052, 2488421201446, 

>    42636471916622, 772807552752712, 14774586965277816, 297138592463202402, 

>    6271277634164008170, 138596853553771517492, 3200958202120445923684, 

>    77114612783976599209598, 1934583996316791634828454, 

>    50460687385591722097602304, 1366482059862153751146376304, 

>    38366771565392871446940748410, 1115482364570332601576605376898, 

>    33544252621178275692411892779180, 1042188051349139920383738392594332, 

>    33419576037745472521641814354312790, 

>    1105004411146009553865786545464526206, 

>    37639281863619947475378460886135133496, 

>    1319658179153254337635342434408766065896, 

>    47585390139805782930448514259179162696722, 

>    1763380871412273296449902785237054760438426, 

>    67106516021125545469475040472412706780911268, 

>    2620784212531087457316728120883870079549134420, 

>    104969402113244439880057492782663678669089779118, 

>    4309132147486627708154774750891684285077633835734, 

>    181199144276064794296827392186304334716629346180848, 

>    7800407552443042507640613928796820288452902805286368, 

>    343589595090843265591418718266306051705639884996218154, 

>    15477521503994968035062094274002250590013877419466108978, 

>    712669883315580566495978374316773450341097231239406211100, 

>    33527174671849317156037438120623503416356879769273672584588, 

>    1610762789255012501855846297689494046193178343355755998487686}
Anders Kaseorg
sumber
3
Pikiranku tertiup angin, pekerjaan bagus
Philippe
6

Jelly , 17 16 byte

ṖḊŒ!ð1;;⁹IỊṀðÐḟL

Tautan monadik.

Cobalah online!

Bagaimana?

ṖḊŒ!ð1;;⁹IỊṀðÐḟL - Link: number n
Ṗ                - pop (implicit range build) -> [1,n-1]
 Ḋ               - dequeue -> [2,n-1]
  Œ!             - all permutations of [2,n-1]
    ð       ðÐḟ  - filter discard those entries for which this is truthy:
     1;          -   1 concatenated with the entry
       ;⁹        -   ...concatenated with right (n)
         I       -   incremental differences
          Ị      -   is insignificant (absolute value <=1)
           Ṁ     -   maximum
               L - length (the number of valid arrangements)
Jonathan Allan
sumber
Maaf tetapi tidak memenuhi kasus uji
Philippe
1
Ya, Anda membuat kesalahan yang sama yang saya lakukan pada awalnya dan Okx. Anda harus memperhitungkan fakta bahwa angka kedua tidak boleh 2 dan angka kedua-ke-terakhir tidak boleh n-1
ETHproduksi
@ Pilip memperbaikinya.
Jonathan Allan
Saya tidak berpikir menggunakan IỊṀitu valid. Secara khusus, bagaimana jika -2ada salah satu delta di sana misalnya? Anda dapat memperbaikinya dengan IAỊṀuntuk +1.
Erik the Outgolfer
1
@ Jonathan Allan Ooh saya pikir itu kembali x <= 1.
Erik the Outgolfer
5

Japt , 19 18 byte

o2 á è_pU äÉ m²e>1

Uji secara online! Saya tidak akan merekomendasikan pengujian pada apa pun yang lebih besar dari 10.

Penjelasan

o2 á è_  pU äÉ  m²  e>1
o2 á èZ{ZpU ä-1 mp2 e>1}
                          : Implicit: U = input integer
o2                        : Create the range [2..U-1].
   á                      : Generate all permutations of this range.
     èZ{               }  : Check how many permutations Z return a truthy value:
        ZpU               :   Push U to the end of Z.
            ä-1           :   Push 1 to the beginning of Z, then take the difference
                          :   of each pair of items.
                m         :   Map each item X to
                 p2       :     X ** 2. This gives a number greater than 1 unless the
                          :     item is 1 or -1.
                    e>1   :   Return whether every item in this list is greater than 1.
                          :   This returns `true` iff the permutation contains no
                          :   consecutive pairs of numbers.
                          : Implicit: output result of last expression
Produksi ETH
sumber
Kerja bagus! Lucu bagaimana kode brute-force saya tidak bisa lebih dari n = 13 tidak ahah
Philippe
@ Pilipe Saya tidak akan merekomendasikan menerima begitu cepat, saya yakin ini akan lebih pendek di 05AB1E atau Jelly ;-)
ETHproductions
Gagal di testcase 1.
Okx
2
@Okx OP telah menetapkan bahwa kita dapat mengasumsikan n > 1.
ETHproduksi
5

05AB1E , 17 byte

L¦¨œʒ¹1Š)˜¥Ä1å_}g

Cobalah online!

Okx
sumber
Maaf, ini tidak memberikan hasil yang tepat
Philippe
@ Pilipe Di testcase mana?
Okx
@ Pilipe Diperbaiki.
Okx
¹1Š)˜menghemat satu byte.
Emigna
5

Haskell, 76 65 byte

Disimpan 11 byte berkat @xnor.

Menggunakan hasil untuk Q_recpada halaman 7 dari temuan @ ChristiaanWesterbeek, kita dapatkan

f 1=1
f n|n<6=0
f n=sum$zipWith((*).f)[n-5..][n-4,1,10-2*n,4,n-2]

Saya tidak mengerti bagaimana hasil mereka selanjutnya haterkait 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 untuk n>=6) yang juga hanya akan membutuhkan memori konstan - jika saja angkanya tidak terus meningkat ...

f n=last$foldl(#)[1,0,0,0,0][6..n]
l#n=tail l++[sum$zipWith(*)l[n-4,1,10-2*n,4,n-2]]

Itu memberi

Prelude> f 50
1610762789255012501855846297689494046193178343355755998487686
Prelude> f 500
659178618863924802757920269977240274180092211041657762693634630044383805576666007245903670780603497370173231423527767109899936008034229541700392144282505597945561328426013937966521561345817045884498867592832897938083071843810602104434376305964577943025310184523643816782047883794585616331928324460394146825636085453532404319881264974005968087265587062691285454120911586459406436421191277596121471930913837355151842093002557978076653884610826296845041929616496533544124347765641367732716560025553179112645454078955409181466212732427071306363820080109636358537270466838558068527692374178581063316309789026101221004745226182671038004326069705775312654329754698423385241664984156235692539255677944294995403233446243315371404887473868003155621849544566385172835597260848972758443874423271017007843907015007416644383573987606586308556317833384896267539628278571497402655322562624217658332870157802254043614726316296058329670971054977099155788604175817828380564156329839201579006169173002756295957371639199917376529472990059986681882194726437566769717959443857298155265292535858523609764515938314672724480762724541633037484152303637096

Tidak masalah juga untuk mendapatkan f 5000tetapi 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 menyukai 1 3 5 7dan 1 5 3 7memiliki kelanjutan valid yang sama persis, jadi atasi semuanya. Dengan menggunakan ide-ide ini, saya bisa menghitung nilai hingga n=16 0,3 detik.

Sievers Kristen
sumber
Anda dapat menulis ekspresi rekursif yang lebih pendek seperti titik dengan mengekstraksi keluar koefisien: f n=sum$zipWith((*).f)[n-5..][n-4,1,10-2*n,4,n-2].
xnor
@ xnor Benar, terima kasih!
Christian Sievers
Ini adalah pekerjaan yang bagus, saya kagum dengan hasil yang dihasilkan oleh komunitas ini! Sayang sekali ini golf ^^
Philippe
4

Python, 125 byte

from itertools import*
lambda n:sum(p[-1]-p[0]==n-1and all(~-abs(x-y)for x,y in zip(p,p[1:]))for p in permutations(range(n)))
shooqie
sumber
Terlihat sangat cepat, kerja bagus!
Philippe
2
117 bytes
ovs
3

Mathematica, 66 byte

Count[Permutations@Range@#,x:{1,__,#}/;FreeQ[Differences@x,1|-1]]&

Penjelasan

Functiondengan argumen pertama #.

Count[                                                             (* Count the number of *)
      Permutations@                                                (* permutations of *)
                   Range@#,                                        (* the list {1, ..., #} *)
                           x:{1,__,#}                              (* of the form {1, __, #} *)
                                     /;                            (* such that *)
                                             Differences@x,        (* the list of differences of consecutive elements *)
                                       FreeQ[                      (* is free of elements of the form *)
                                                           1|-1    (* 1 or -1 *)
                                                               ]]&
ngenisis
sumber
3

Javascript (ES6), 100 74 72 60 byte

f=n=>n--<6?!n|0:f(n)*--n+4*f(n--)-2*f(n--)*--n+f(n)*++n+f(n)

Di bawah ini adalah versi sebelum penguasaan-golf @PeterTaylor

f=n=>n<6?n==1|0:(n-4)*f(n-5)+f(n-4)-2*(n-5)*f(n-3)+4*f(n-2)+(n-2)*f(n-1)

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

for (i=1; i<=20; i++) {
  console.log(i, f(i))
}

1 1 
2 0 
3 0 
4 0 
5 0 
6 2 
7 10 
8 68 
9 500 
10 4174 
11 38774 
12 397584 
13 4462848 
14 54455754 
15 717909202 
16 10171232060 
17 154142811052 
18 2488421201446 
19 42636471916622 
20 772807552752712
Christiaan Westerbeek
sumber
1
Deskripsi tugas hanya menanyakan f(n)kapan n>1, jadi tidak masalah untuk apa Anda kembali n=1. Saya juga berpikir f(1)=1itu benar.
Christian Sievers
Anda dapat menggabungkan kasing khusus n<6?n==1|0:untuk penghematan dua char selanjutnya.
Peter Taylor
Bagus. Saya menyesuaikan 2 komentar tersebut.
Christiaan Westerbeek
1
Dan dengan menata ulang persyaratan dan mengandalkan urutan evaluasi, Anda dapat mencapai 60:f=n=>n--<6?!n|0:f(n)*--n+4*f(n--)-2*f(n--)*--n+f(n)*++n+f(n)
Peter Taylor
1

Brachylog , 26 byte

{⟦₁pLh1&~tLs₂ᶠ{-ȧ>1}ᵐ}ᶜ|∧0

Cobalah online!

Penjelasan

{                    }ᶜ       Output = count the number of outputs of:
 ⟦₁pL                           L is a permutation of [1, …, Input]
    Lh1                         The head of L is 1
       &~tL                     The tail of L is the Input
          Ls₂ᶠ                  Find all sublists of length 2 of L
              {    }ᵐ           Map on each sublist:
               -ȧ>1               The elements are separated by strictly more than 1
                       |      Else (no outputs to the count)
                        ∧0    Output = 0
Fatalisasi
sumber
1

Python 3 , 109 107 102 byte

q=lambda s,x,n:sum(q(s-{v},v,n)for v in s if(v-x)**2>1)if s else x<n;f=lambda n:q({*range(2,n)},1,n-1)

Cobalah online!

Dihapus empat byte dengan tidak mencoba fungsi satu-baris (seperti yang disarankan oleh @shooqie) dan byte lain dengan mengganti absdengan kuadrat. (Membutuhkan Python 3.5+)

Rici
sumber
103 byte
shooqie
0

Python 2 , 136 byte

-10 byte terima kasih kepada @ovs.

lambda n,r=range:sum(x[0]<1and~-n==x[-1]and 2+~any(abs(x[i]-x[i+1])<2for i in r(n-1))for x in permutations(r(n)))
from itertools import*

Cobalah online!

Tuan Xcoder
sumber
136 bytes
ovs
0

Mathematica, 134 byte

(s=Permutations@Range[2,#-1];g=Table[Join[Prepend[s[[i]],1],{#}],{i,Length@s}];Length@Select[Union@*Abs@*Differences/@g,FreeQ[#,1]&])&


test case n: 2 hingga 12

{0, 0, 0, 0, 2, 10, 68, 500, 4174, 38774, 397584}

J42161217
sumber
0

Python 2 , 105 byte

lambda n:reduce(lambda a,i:a+[i*a[-5]+a[-4]+2*(1-i)*a[-3]+4*a[-2]+(i+2)*a[-1]],range(2,n),[0,1]+4*[0])[n]

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, reducetelah dipindahkan ke functools.)

Ada versi yang jauh lebih singkat menggunakan produk dot numpy, tetapi meluap cukup cepat dan membutuhkan numpy telah diimpor. Tapi untuk apa nilainya:

lambda n:reduce(lambda a,i:a+[dot([i,1,2-2*i,4,i+2],a[-5:])],range(2,n),[0,1]+4*[0])[n]
Rici
sumber