Liczba Bell ( OEIS A000110 ) jest kilka sposobów do podsystemu zbiór N oznaczonych (odrębne) elementów. Numer 0 dzwonka jest zdefiniowany jako 1.

Spójrzmy na kilka przykładów (używam nawiasów, aby oznaczyć podzbiory i nawiasy klamrowe dla partycji):

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

Istnieje wiele sposobów obliczania numerów dzwonków i możesz dowolnie z nich korzystać. Tutaj zostanie opisany jeden sposób:

Najłatwiejszym sposobem obliczenia liczb Bell jest użycie trójkąta liczbowego przypominającego trójkąt Pascala dla współczynników dwumianowych. Numery dzwonków pojawiają się na krawędziach trójkąta. Zaczynając od 1, każdy nowy rząd w trójkącie jest konstruowany poprzez pobranie ostatniego wpisu w poprzednim rzędzie jako pierwszego, a następnie ustawienie każdego nowego wpisu do jego lewego sąsiada plus jego górnego lewego sąsiada:

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

Możesz użyć indeksowania 0 lub indeksowania 1. Jeśli używasz indeksowania 0, wejście 3powinno wypisywać 5, ale powinno wypisywać, 2jeśli używasz indeksowania 1.

Twój program musi działać do 15. numeru dzwonka, wysyłając 1382958545. Teoretycznie twój program powinien być w stanie obsługiwać większe liczby (innymi słowy, nie koduj rozwiązań na stałe). EDYCJA: Nie musisz obsługiwać danych wejściowych 0 (dla indeksowania 0) lub 1 (dla indeksowania 1), ponieważ nie są one obliczane metodą trójkąta.

Przypadki testowe (przy założeniu indeksowania 0):

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

Odpowiedzi przy użyciu wbudowanej metody (takiej jak BellB [n] w języku Wolfram), która bezpośrednio wytwarza liczby Bell, będą niekonkurencyjne.

Najkrótszy kod (w bajtach) wygrywa.

Galaretka , 9 bajtów

ṖµṀcæ.߀‘

To używa formuły

który jest zamknięty, gdy n <2 .

Wypróbuj online!

Jak to działa

ṖµṀ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.

JavaScript (ES6), 47 bajtów

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

Pierwszy ma indeks 0, drugi indeks 1.

Haskell, 36 bajtów

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

Używa metody trójkąta, poprawnie obsługuje 0, 0.

R , 31 bajtów

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

używa wzoru Stirlinga z drugiego rodzaju i oblicza te liczby za pomocą pakietu gmp ; odczytuje ze standardowego wejścia i zwraca wartość jako Big Integer; kończy się niepowodzeniem dla 0; 1-indeksowany.

Mathematica, 24 bajty

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

-13 bajtów od @Kelly Lowder!

Galaretka , 14 12 11 bajtów

ṫ0;⁸+\
1Ç¡Ḣ

Wypróbuj online!

Nie trafiłem dokładnie w mocne strony Jelly z dynamicznym wejściem ¡, Ṫ zawsze modyfikując tablicę i brak wyprzedzającego atomu (jednobajtowy ;@lub odwrotny ṭ).

CJam (19 bajtów)

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

Demo online

Sekcja

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

MATL , 14 bajtów

:dtEw1Zh1Ze/Yo

Dane wejściowe są oparte na 0. Wypróbuj online!

Wyjaśnienie

To używa formuły

gdzie _p F _q ( a ₁ , ..., a _p ; b ₁ , ..., b _q ; x ) jest uogólnioną funkcją hipergeometryczną .

:      % 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

Python , 42 bajty

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

Wypróbuj online!

Recursywna formuła pochodzi z umieszczania nelementów w partycjach. Z kolei dla każdego elementu decydujemy, czy go umieścić:

• Na istniejącą partycję, z której istnieją kopcje
• Aby rozpocząć nową partycję, która zwiększa liczbę opcji kdla przyszłych elementów

Tak czy inaczej zmniejsza pozostałą liczbę nelementów do umieszczenia. Mamy więc formułę rekurencyjną f(n,k)=k*f(n-1,k)+f(n-1,k+1)i f(0,k)=1, z f(n,0)n-tym numerem Bell.

Python 2 , 91 bajtów

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))

Wypróbuj online!

B (n) obliczone jako suma liczb Stirlinga drugiego rodzaju.

MATLAB, 128 103 bajtów

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)

Dość oczywiste. Pominięcie średnika na końcu linii powoduje wydrukowanie wyniku.

25 bajtów zaoszczędzonych dzięki Luisowi Mendo.

R , 46 bajtów

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

Wypróbuj online!

MATL , 19 18 bajtów

1i:"t@q@:qXn*sh]0)

Wykorzystuje dane wejściowe oparte na 0. Na podstawie relacji nawrotu

Wypróbuj online!

Ohm , 15 bajtów

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

Wypróbuj online!

Korzysta z forum Dobińskiego (działa nawet dla B (0) yay ).

Wyjaśnienie

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???)

Python (79 bajtów)

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 w Python 2, ale działa również w Python 3.

To buduje trójkąt Aitkena za pomocą rekurencyjnej lambda dla golfowej pętli.

Haskell , 35 bajtów

(%0)
n%k|n<1=1|m<-n-1=k*m%k+m%(k+1)

Wypróbuj online!

Formula wyjaśniona w mojej odpowiedzi w języku Python .

J, 17 bajtów

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

Używa metody obliczania trójkąta.

Wypróbuj online!

Wyjaśnienie

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)

Python 3 , 78 bajtów

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

Postanowiłem spróbować obrać inną drogę do obliczeń. To używa formuły Dobińskiego, 0-indeksowane, nie działa dla 0.

Wypróbuj online!

Python 3 , 68 60 bajtów

Prosta rekurencyjna konstrukcja trójkąta, ale jest niezwykle nieefektywna ze względów praktycznych. Obliczenie do 15. numeru dzwonka powoduje przekroczenie limitu czasu TIO, ale działa na moim komputerze.

Używa 1-indeksowania i zwraca Truezamiast 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)

Wypróbuj online!

Dzięki @FelipeNardiBatista za oszczędność 8 bajtów!

PHP , 72 bajty

funkcja rekurencyjna 1-indeksowana

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

Wypróbuj online!

PHP , 86 bajtów

0-indeksowane

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

Wypróbuj online!

PHP , 89 bajtów

funkcja rekurencyjna indeksowana 0

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;}

Wypróbuj online!

Alice , 22 bajty

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

Wypróbuj online!

Używa to metody trójkąta. Dla n = 0 oblicza to B (1), co jest dogodnie równe B (0).

Wyjaśnienie

Jest to standardowy szablon dla programów, które pobierają dane w trybie porządkowym, przetwarzają je w trybie kardynalnym i wyprowadzają wynik w trybie porządkowym. 1Do szablonu dodano A, aby umieścić tę wartość na stosie poniżej danych wejściowych.

Program używa stosu jako rozwijającej się kolejki kołowej do obliczania każdego rzędu trójkąta. Podczas każdej iteracji po pierwszej, jedno niejawne zero poniżej stosu staje się jawnym zerem.

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

Pierwsza iteracja skutecznie zakłada początkową głębokość stosu równą zero, pomimo wymaganej 1 na górze stosu. W rezultacie 1 zostaje dodane do siebie, a cały trójkąt jest mnożony przez 2. Dzielenie wyniku końcowego przez 2 daje poprawną odpowiedź.

Pari / GP , 36 bajtów

n->n!*Vec(exp(exp(x+O(x^n++))-1))[n]

Wypróbuj online!