Podaj n-ty numer dzwonka

13

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.

code-golf math takielunek
źródło
Jeśli użyjesz indeksowania 0, wejście 3powinno5 wypisać To wyrzuciłoby 15, prawda? I z 1-indeksowaniem dałoby wynik5
Luis Mendo
Powodem tego było zliczanie numeru 0 dzwonka jako indeksu 0 w indeksowaniu 0 i indeksu 1 w indeksowaniu 1. Twoja droga może być bardziej przejrzysta, ale istniejące odpowiedzi działają w ten sposób, więc nie mogę tego teraz zmienić. Właśnie dołączyłem do tej witryny kilka godzin temu
sfałszowałem
Ale mówisz, że przy indeksowaniu 1 dane 3wyjściowe powinny być wyprowadzane 2. Co wtedy 1da dane wejściowe przy indeksowaniu 1?
Luis Mendo,
1 -> 1, 2 -> 1, 3 -> 2 (odpowiadające numerom 0, 1 i 2 dzwonka) w przeciwieństwie do 0 -> 1, 1 -> 1, 2 -> 2 Może używam złego terminologia
sfałszowany
Myślę, że rozumiem. Brakuje pierwszego 1 w przykładowej tabeli i wynikach, co mnie
pomyliło

Odpowiedzi:

2

Galaretka , 9 bajtów

ṖµṀcæ.߀‘

To używa formuły

formuła

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.
Dennis
źródło
8

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.

Neil
źródło
8

Haskell, 36 bajtów

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

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

Christian Sievers
źródło
5

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.

Giuseppe
źródło
4

Mathematica, 24 bajty

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

-13 bajtów od @Kelly Lowder!

J42161217
źródło
Sum[k^#/k!,{k,0,∞}]/E&ma tylko 24 bajty
Kelly Lowder
3

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

PurkkaKoodari
źródło
3

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
Peter Taylor
źródło
3

MATL , 14 bajtów

:dtEw1Zh1Ze/Yo

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

Wyjaśnienie

To używa formuły

wprowadź opis zdjęcia tutaj

gdzie p F q ( a 1 , ..., a p ; b 1 , ..., 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
Luis Mendo
źródło
3

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.

xnor
źródło
2

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.

Chas Brown
źródło
To miłe rozwiązanie. Zauważ, że użycie wbudowanego dla liczb Stirlinga drugiego rodzaju pozwoliłoby na obliczenie liczb Bell (jeśli używasz Mathematica lub podobnego)
sfałszowane
Możesz zapisać dwa bajty bezpośrednio w definicji s: ponieważ wywołania rekurencyjne zawsze zmniejszają się ni nie ma podziału przez kciebie, możesz stracić *kw pierwszym okresie.
Peter Taylor
Lub możesz uratować pęczek, spłaszczając do jednej lambdy, pracując na całych rzędach: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
jako czynność Bnie jest rekurencyjny i to jest twoja ostateczna odpowiedź, można pominąć B=, aby zaoszczędzić 2 bajty
Felipe Nardi Batista
2

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.

takielunek
źródło
2

R , 46 bajtów

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

Wypróbuj online!

Leaky Nun
źródło
42 bajty - Tdomyślnie TRUE(aka 1), chyba że zostało ustawione gdzie indziej
Giuseppe
2

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???)
Datboi
źródło
2

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.

Peter Taylor
źródło
1

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)
mile
źródło
1

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!

C McAvoy
źródło
1
ponieważ twoja funkcja fnie jest rekurencyjna, możesz pominąć f=i zapisać 2 bajty
Felipe Nardi Batista
1

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!

Chase Vogeli
źródło
60 bajtów . zwracanie wartości logicznych zamiast liczb (0,1) jest dopuszczalne w pythonie
Felipe Nardi Batista
1

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!

Jörg Hülsermann
źródło
1

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ź.

Nitrodon
źródło