Keluarkan Nomor Bel ke-n

13

Sebuah jumlah Bell ( Oei A000110 ) adalah sejumlah cara untuk partisi satu set n berlabel (berbeda) elemen. Nomor Bell 0 didefinisikan sebagai 1.

Mari kita lihat beberapa contoh (saya menggunakan tanda kurung untuk menunjukkan subset dan kurung untuk partisi):

1: {1}
2: {[1,2]}, {[1],[2]}
3: {[1,2,3]}, {[1,2],[3]}, {[1,3],[2]}, {[2,3],[1]}, {[1],[2],[3]}

Ada banyak cara untuk menghitung nomor Bell, dan Anda bebas untuk menggunakannya. Satu cara akan dijelaskan di sini:

Cara termudah untuk menghitung nomor Bell adalah dengan menggunakan segitiga nomor yang menyerupai segitiga Pascal untuk koefisien binomial. Nomor Bell muncul di tepi segitiga. Dimulai dengan 1, setiap baris baru dalam segitiga dibangun dengan mengambil entri terakhir di baris sebelumnya sebagai entri pertama, dan kemudian mengatur setiap entri baru ke tetangga kirinya ditambah tetangga kiri atas:

1
1    2
2    3    5
5    7   10   15
15  20   27   37   52

Anda dapat menggunakan pengindeksan 0 atau pengindeksan 1. Jika Anda menggunakan pengindeksan-0, sebuah input 3harus di-output 5, tetapi harus di-output 2jika Anda menggunakan pengindeksan-1.

Program Anda harus bekerja hingga nomor Bell 15, mengeluarkan 1382958545. Secara teori, program Anda harus dapat menangani angka yang lebih besar (dengan kata lain, jangan membuat hardcode solusinya). EDIT: Anda tidak diharuskan untuk menangani input 0 (untuk pengindeksan 0) atau 1 (untuk pengindeksan 1) karena tidak dihitung dengan metode segitiga.

Kasus uji (dengan asumsi 0-indexing):

0 ->  1 (OPTIONAL)
1 ->  1 
2 ->  2 
3 ->  5 
4 ->  15 
5 ->  52 
6 ->  203 
7 ->  877 
8 ->  4140 
9 ->  21147 
10 -> 115975 
11 -> 678570 
12 -> 4213597 
13 -> 27644437 
14 -> 190899322 
15 -> 1382958545

Jawaban menggunakan metode bawaan (seperti BellB [n] dalam Bahasa Wolfram) yang secara langsung menghasilkan nomor Bell akan menjadi tidak kompetitif.

Kode terpendek (dalam byte) menang.

code-golf math dicurangi
sumber
Jika Anda menggunakan pengindeksan 0, sebuah input dari 3harus menampilkan5 Ini akan keluar 15, kan? Dan dengan 1-pengindeksan itu akan menampilkan5
Luis Mendo
Alasan di balik itu adalah menghitung nomor lonceng 0 sebagai indeks 0 dalam pengindeksan 0 dan indeks 1 dalam pengindeksan. Cara Anda mungkin lebih jelas, tetapi jawaban yang ada berfungsi seperti itu, jadi saya tidak bisa mengubahnya sekarang. Saya baru saja bergabung dengan situs ini beberapa jam yang lalu
dicurangi
Tetapi Anda mengatakan bahwa dengan pengindeksan 1, input 3harus keluar 2. Lalu apa yang akan input 1berikan dengan pengindeksan 1?
Luis Mendo
1 -> 1, 2 -> 1, 3 -> 2 (sesuai dengan nomor Bell 0, 1, dan 2) dibandingkan dengan 0 -> 1, 1 -> 1, 2 -> 2 Mungkin saya menggunakan yang salah terminologi
dicurangi
Saya rasa saya mengerti. 1 yang pertama tidak ada pada tabel contoh dan output Anda, yang membingungkan saya
Luis Mendo

Jawaban:

2

Jelly , 9 byte

ṖµṀcæ.߀‘

Ini menggunakan rumus

rumus

yang ditutup setiap kali n <2 .

Cobalah online!

Bagaimana itu bekerja

ṖµṀcæ.߀‘  Main link. Argument: n

Ṗ          Pop; yield A := [1, ..., n-1].
 µ         Begin a new, monadic chain with argument A.
  Ṁ        Maximum; yield n-1.
   c       Combinatons; compute (n-1)C(k) for each k in A.
      ߀   Recursively map the main link over A.
    æ.     Take the dot product of the results to both sides.
        ‘  Increment; add 1 to the result.
Dennis
sumber
8

JavaScript (ES6), 47 byte

f=(n,a=[b=1])=>n--?f(n,[b,...a.map(e=>b+=e)]):b
f=(n,a=[b=1])=>--n?f(n,[b,...a.map(e=>b+=e)]):b

Yang pertama diindeks 0, kedua diindeks.

Neil
sumber
8

Haskell, 36 byte

head.(iterate(last>>=scanl(+))[1]!!)

Menggunakan metode segitiga, dengan benar menangani 0, 0 berbasis.

Sievers Kristen
sumber
5

R , 31 byte

sum(gmp::Stirling2.all(scan()))

menggunakan rumus Stirling Number dari Jenis Kedua dan menghitung angka-angka itu dengan paket gmp ; membaca dari stdin dan mengembalikan nilainya sebagai Big Integer; gagal untuk 0; 1-diindeks.

Giuseppe
sumber
4

Mathematica, 24 byte

Sum[k^#/k!,{k,0,∞}]/E&

-13 byte dari @Kelly Lowder!

J42161217
sumber
Sum[k^#/k!,{k,0,∞}]/E&hanya 24 byte
Kelly Lowder
3

Jelly , 14 12 11 byte

ṫ0;⁸+\
1Ç¡Ḣ

Cobalah online!

Tidak tepat mengenai titik kuat Jelly dengan input dinamis ¡, Ṫ selalu memodifikasi array dan kurangnya atom yang saling bergantung (satu byte ;@atau sebaliknya ṭ).

PurkkaKoodari
sumber
3

CJam (19 byte)

Xa{X\{X+:X}%+}qi*0=

Demo online

Pembedahan

Xa         e# Start with an array [1]
{          e# Repeat...
  X\       e#   Put a copy of X under the current row
  {X+:X}%  e#   Map over x in row: push (X+=x)
  +        e#   Prepend that copy of last element of the previous row to get the next row
}
qi*        e# ... input() times
0=         e# Select the first element
Peter Taylor
sumber
3

MATL , 14 byte

:dtEw1Zh1Ze/Yo

Input berbasis 0. Cobalah online!

Penjelasan

Ini menggunakan rumus

masukkan deskripsi gambar di sini

di mana p F q ( a 1 , ..., a p ; b 1 , ..., b q ; x ) adalah fungsi hypergeometric umum .

:      % Implictly input n. Push array [1 2 ... n]
d      % Consecutive differences: array [1 ... 1] (n-1 entries)
tE     % Duplicate, multiply by 2: array [2 ... 2] (n-1 entries)
w      % Swap
1      % Push 1
Zh     % Hypergeometric function
1Ze    % Push number e
/      % Divide
Yo     % Round (to prevent numerical precision issues). Implicitly display
Luis Mendo
sumber
3

Python , 42 byte

f=lambda n,k=0:n<1or k*f(n-1,k)+f(n-1,k+1)

Cobalah online!

Rumus rekursif berasal dari menempatkan nelemen ke dalam partisi. Untuk setiap elemen pada gilirannya, kami memutuskan apakah akan menempatkannya:

  • Ke dalam partisi yang ada, di mana ada kpilihan
  • Untuk memulai partisi baru, yang meningkatkan jumlah pilihan kuntuk elemen masa depan

Either way mengurangi jumlah nelemen yang tersisa untuk ditempatkan. Jadi, kami memiliki rumus rekursif f(n,k)=k*f(n-1,k)+f(n-1,k+1)dan f(0,k)=1, dengan f(n,0)nomor Bell ke-n.

Tidak
sumber
2

Python 2 , 91 byte

s=lambda n,k:n*k and k*s(n-1,k)+s(n-1,k-1)or n==k
B=lambda n:sum(s(n,k)for k in range(n+1))

Cobalah online!

B (n) dihitung sebagai jumlah angka Stirling dari jenis kedua.

Chas Brown
sumber
Itu solusi yang bagus. Perhatikan bahwa menggunakan built-in untuk nomor Stirling dari jenis kedua akan diizinkan untuk menghitung nomor Bell (jika menggunakan Mathematica atau yang serupa)
dicurangi
Anda dapat menyimpan dua byte secara langsung dalam definisi s: karena panggilan rekursif selalu berkurang ndan tidak ada pembagian oleh kAnda dapat kehilangan *kdalam istilah pertama.
Peter Taylor
Atau Anda dapat menyimpan banyak dengan meratakan menjadi satu lambda, mengerjakan seluruh baris:B=lambda n,r=[1,0]:n and B(n-1,[k*r[k]+r[k-1]for k in range(len(r))]+[0])or sum(r)
Peter Taylor
karena fungsi Anda Btidak rekursif dan itu adalah jawaban akhir Anda, Anda dapat menghilangkan B=untuk menyimpan 2 byte
Felipe Nardi Batista
2

MATLAB, 128 103 byte

function q(z)
r(1,1)=1;for x=2:z
r(x,1)=r(x-1,x-1);for y=2:x
r(x,y)=r(x,y-1)+r(x-1,y-1);end
end
r(z,z)

Cukup jelas. Menghilangkan titik koma di akhir baris akan mencetak hasilnya.

25 byte disimpan berkat Luis Mendo.

dicurangi
sumber
2

R , 46 byte

r=1;for(i in 1:scan())r=cumsum(c(r[i],r));r[1]

Cobalah online!

Biarawati Bocor
sumber
42 byte - Tdefault ke TRUE(alias 1) kecuali sudah disetel di tempat lain
Giuseppe
2

Ohm , 15 byte

2°M^┼ⁿ^!/Σ;αê/≈

Cobalah online!

Menggunakan forumla Dobinski (bahkan berfungsi untuk B (0) yay ).

Penjelasan

2°M^┼ⁿ^!/Σ;αê/≈
2°        ;     # Push 100
  M             # Do 100 times...
   ^             # Push index of current iteration
    ┼ⁿ           # Take that to the power of the user input
      ^!         # Push index factorial
        /        # Divide
         Σ       # Sum stack together
           αê   # Push e (2.718...)
             /  # Divide
              ≈ # Round to nearest integer (Srsly why doesn't 05AB1E have this???)
Datboi
sumber
2

Python (79 byte)

B=lambda n,r=[1]:n and B(n-1,[r[-1]+sum(r[:i])for i in range(len(r)+1)])or r[0]

Demo online di Python 2, tetapi juga berfungsi di Python 3.

Ini membangun segitiga Aitken menggunakan lambda rekursif untuk loop golf.

Peter Taylor
sumber
1

J, 17 byte

0{]_1&({+/\@,])1:

Menggunakan metode perhitungan segitiga.

Cobalah online!

Penjelasan

0{]_1&({+/\@,])1:  Input: integer n
               1:  The constant 1
  ]                Identity function, get n
   _1&(       )    Call this verb with a fixed left argument of -1 n times
                   on itself starting with a right argument [1]
             ]       Get right argument
       {             Select at index -1 (the last item)
            ,        Join
        +/\@         Find the cumulative sums
0{                 Select at index 0 (the first item)
mil
sumber
1

Python 3 , 78 byte

from math import*
f=lambda n:ceil(sum(k**n/e/factorial(k)for k in range(2*n)))

Saya memutuskan untuk mencoba dan menempuh rute berbeda untuk perhitungan. Ini menggunakan rumus Dobinski, diindeks 0, tidak berfungsi untuk 0.

Cobalah online!

C McAvoy
sumber
1
karena fungsi Anda ftidak berulang, Anda dapat menghilangkan f=dan menyimpan 2 byte
Felipe Nardi Batista
1

Python 3 , 68 60 byte

Konstruksi segitiga rekursif yang sederhana, tetapi sangat tidak efisien untuk tujuan praktis. Menghitung hingga nomor Bell ke-15 menyebabkan TIO kehabisan waktu, tetapi berfungsi pada mesin saya.

Ini menggunakan pengindeksan 1, dan mengembalikan Truebukan 1.

f=lambda r,c=0:r<1or c<1and f(r-1,r-1)or f(r-1,c-1)+f(r,c-1)

Cobalah online!

Terima kasih kepada @FelipeNardiBatista karena telah menghemat 8 byte!

Chase Vogeli
sumber
60 byte . mengembalikan boolean alih-alih angka (0,1) dapat diterima dalam python
Felipe Nardi Batista
1

PHP , 72 byte

fungsi rekursif 1-diindeks 

function f($r,$c=0){return$r?$c?f($r-1,$c-1)+f($r,$c-1):f($r-1,$r-2):1;}

Cobalah online!

PHP , 86 byte

Diindeks 0 

for(;$r++<$argn;)for($c=~0;++$c<$r;)$l=$t[$r][$c]=$c?$l+$t[$r-1][$c-1]:($l?:1);echo$l;

Cobalah online!

PHP , 89 byte

fungsi rekursif 0-diindeks 

function f($r,$s=NULL){$c=$s??$r-1;return$r>1?$c?f($r-1,$c-1)+f($r,$c-1):f($r-1,$r-2):1;}

Cobalah online!

Jörg Hülsermann
sumber
1

Alice , 22 byte

/oi
\1@/t&wq]&w.q,+k2:

Cobalah online!

Ini menggunakan metode segitiga. Untuk n = 0, ini menghitung B (1) sebagai gantinya, yang nyaman sama dengan B (0).

Penjelasan

Ini adalah templat standar untuk program yang mengambil input dalam mode ordinal, memprosesnya dalam mode kardinal, dan output hasilnya dalam mode ordinal. SEBUAH1 telah ditambahkan ke template untuk meletakkan nilai itu di tumpukan di bawah input.

Program ini menggunakan tumpukan sebagai antrian melingkar yang membesar untuk menghitung setiap baris segitiga. Selama setiap iterasi melewati yang pertama, satu nol implisit di bawah tumpukan menjadi nol eksplisit.

1     Append 1 to the implicit empty string on top of the stack
i     Get input n
t&w   Repeat outer loop that many times (push return address n-1 times)
q     Get tape position (initially zero)
]     Move right on tape
&w    On iteration k, push this return address k-1 times
      The following inner loop is run once for each entry in the next row
.     Duplicate top of stack (the last number calculated so far)
q,    Move the entry k spaces down to the top of the stack: this is the appropriate entry
      in the previous row, or (usually) an implicit zero if we're in the first column
+     Add these two numbers
k     Return to pushed address: this statement serves as the end of two loops simultaneously
2:    Divide by two: see below
o     Output as string
@     Terminate

Iterasi pertama secara efektif mengasumsikan kedalaman tumpukan awal nol, meskipun diperlukan 1 di bagian atas tumpukan. Akibatnya, 1 akhirnya ditambahkan ke dirinya sendiri, dan seluruh segitiga dikalikan dengan 2. Membagi hasil akhir dengan 2 memberikan jawaban yang benar.

Nitrodon
sumber