Salida del n-ésimo número de campana

13

Un número de Bell ( OEIS A000110 ) es el número de formas de particionar un conjunto de n elementos etiquetados (distintos). El número de 0th Bell se define como 1.

Veamos algunos ejemplos (uso corchetes para denotar los subconjuntos y llaves de las particiones):

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

Hay muchas formas de calcular los números de Bell, y usted es libre de usar cualquiera de ellos. Aquí se describirá una forma:

La forma más fácil de calcular los números de Bell es usar un triángulo numérico que se asemeje al triángulo de Pascal para los coeficientes binomiales. Los números de la campana aparecen en los bordes del triángulo. Comenzando con 1, cada nueva fila en el triángulo se construye tomando la última entrada de la fila anterior como la primera entrada y luego configurando cada nueva entrada a su vecino izquierdo más su vecino superior izquierdo:

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

Puede usar 0-indexing o 1-indexing. Si usa la indexación 0, 3debería producirse una entrada de 5, pero debería salir 2si usa la indexación 1.

Su programa debe funcionar hasta el número 15 de la campana, con salida 1382958545. En teoría, su programa debería poder manejar números más grandes (en otras palabras, no codifique las soluciones). EDITAR: No es necesario que maneje una entrada de 0 (para indexación 0) o 1 (para indexación 1) porque no se calcula mediante el método del triángulo.

Casos de prueba (suponiendo 0-indexación):

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

Las respuestas que usen un método incorporado (como BellB [n] en Wolfram Language) que produce directamente números de Bell no serán competitivas.

El código más corto (en bytes) gana.

code-golf math equipado
fuente
Si utiliza 0 indexación, una entrada de 3salida debe5 Sería ouput 15, ¿verdad? Y con la indexación 1 produciría5
Luis Mendo
El razonamiento detrás de eso fue contar el número de campana 0 como índice 0 en indexación 0 e índice 1 en indexación 1. Su camino puede ser más claro, pero las respuestas existentes funcionan así, por lo que no puedo cambiarlo ahora. Me he unido a este sitio hace unas horas
aparejado
Pero usted dice que con la indexación 1, la entrada 3debería salir 2. Entonces, ¿qué daría input 1con 1-indexing?
Luis Mendo
1 -> 1, 2 -> 1, 3 -> 2 (correspondiente a los números 0º, 1º y 2º de campana) en lugar de 0 -> 1, 1 -> 1, 2 -> 2 Tal vez estoy usando el número incorrecto terminología
aparejado el
Creo que lo entiendo. Falta el primer 1 en su tabla de ejemplo y salida, lo que me confundió
Luis Mendo

Respuestas:

2

Jalea , 9 bytes

ṖµṀcæ.߀‘

Esto usa la fórmula

fórmula

que se cierra cada vez que n <2 .

Pruébalo en línea!

Cómo funciona

ṖµṀ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
fuente
8

JavaScript (ES6), 47 bytes

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

El primero está indexado a 0, el segundo está indexado a 1.

Neil
fuente
8

Haskell, 36 bytes

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

Utiliza el método del triángulo, maneja correctamente 0, basado en 0.

Christian Sievers
fuente
4

Mathematica, 24 bytes

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

-13 bytes de @Kelly Lowder!

J42161217
fuente
Sum[k^#/k!,{k,0,∞}]/E&solo tiene 24 bytes
Kelly Lowder
3

Jalea , 14 12 11 bytes

ṫ0;⁸+\
1Ç¡Ḣ

Pruébalo en línea!

No golpeó exactamente los puntos fuertes de Jelly con una entrada dinámica ¡, Ṫ siempre modificando la matriz y la falta de un átomo previo (un byte ;@o inverso ṭ).

PurkkaKoodari
fuente
3

CJam (19 bytes)

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

Demostración en línea

Disección

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
fuente
3

MATL , 14 bytes

:dtEw1Zh1Ze/Yo

La entrada está basada en 0. Pruébalo en línea!

Explicación

Esto usa la fórmula

ingrese la descripción de la imagen aquí

donde p F q ( a 1 , ..., a p ; b 1 , ..., b q ; x ) es la función hipergeométrica generalizada .

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

Python , 42 bytes

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

Pruébalo en línea!

La fórmula recursiva proviene de colocar nelementos en particiones. Para cada elemento a su vez, decidimos si colocarlo:

  • En una partición existente, de la cual hay kopciones
  • Para iniciar una nueva partición, lo que aumenta el número de opciones kpara elementos futuros

De cualquier manera, disminuye el número restante nde elementos para colocar. Entonces, tenemos la fórmula recursiva f(n,k)=k*f(n-1,k)+f(n-1,k+1)y f(0,k)=1, con f(n,0)el enésimo número de Bell.

xnor
fuente
2

Python 2 , 91 bytes

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

Pruébalo en línea!

B (n) calculado como una suma de números de Stirling del segundo tipo.

Chas Brown
fuente
Esa es una buena solución. Tenga en cuenta que el uso de números incorporados para Stirling del segundo tipo podría calcular los números de Bell (si se usa Mathematica o similar)
manipulado el
Puede guardar dos bytes directamente en la definición de s: ya que las llamadas recursivas siempre se reducen ny no hay división por la kque puede perder *ken el primer término.
Peter Taylor
O puede guardar un montón aplanándolo en una lambda, trabajando en filas enteras: 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
ya que su función Bno es recursivo y es su respuesta final, se puede omitir el B=de salvar a 2 bytes
Felipe Batista Nardi
2

MATLAB, 128 103 bytes

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)

Bastante autoexplicativo. Omitir un punto y coma al final de una línea imprime el resultado.

25 bytes guardados gracias a Luis Mendo.

equipado
fuente
2

R , 46 bytes

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

Pruébalo en línea!

Monja permeable
fuente
42 bytes : el valor Tpredeterminado es TRUE(también conocido como 1) a menos que se haya configurado en otro lugar
Giuseppe
2

Ohm , 15 bytes

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

Pruébalo en línea!

Utiliza la forumla de Dobinski (incluso funciona para B (0) yay ).

Explicación

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
fuente
2

Python (79 bytes)

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]

Demostración en línea en en Python 2, pero también funciona en Python 3.

Esto construye el triángulo de Aitken usando una lambda recursiva para un circuito de golf.

Peter Taylor
fuente
1

J, 17 bytes

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

Utiliza el método de cálculo del triángulo.

Pruébalo en línea!

Explicación

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)
millas
fuente
1

Python 3 , 78 bytes

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

Decidí probar y tomar una ruta diferente para el cálculo. Esto usa la fórmula de Dobinski, indexada en 0, no funciona para 0.

Pruébalo en línea!

C McAvoy
fuente
1
como su función fno es recursiva, puede omitir f=y guardar 2 bytes
Felipe Nardi Batista
1

Python 3 , 68 60 bytes

Construcción recursiva simple del triángulo, pero es muy ineficiente para fines prácticos. Calcular hasta el número 15 de la campana hace que TIO agote el tiempo de espera, pero funciona en mi máquina.

Esto utiliza la indexación 1 y devuelve en Truelugar de 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)

Pruébalo en línea!

¡Gracias a @FelipeNardiBatista por guardar 8 bytes!

Chase Vogeli
fuente
60 bytes . regresar booleanos en lugar de números (0,1) es aceptable en python
Felipe Nardi Batista
1

PHP , 72 bytes

función recursiva 1 indexada 

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

Pruébalo en línea!

PHP , 86 bytes

0 indexado 

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

Pruébalo en línea!

PHP , 89 bytes

función recursiva indexada 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;}

Pruébalo en línea!

Jörg Hülsermann
fuente
1

Alice , 22 bytes

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

Pruébalo en línea!

Esto usa el método del triángulo. Para n = 0, esto calcula B (1) en su lugar, que es convenientemente igual a B (0).

Explicación

Esta es una plantilla estándar para programas que toman la entrada en modo ordinal, la procesan en modo cardinal y generan el resultado en modo ordinal. UN1 ha agregado A a la plantilla para poner ese valor en la pila debajo de la entrada.

El programa usa la pila como una cola circular en expansión para calcular cada fila del triángulo. Durante cada iteración pasada la primera, un cero implícito debajo de la pila se convierte en un cero explícito.

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

La primera iteración asume efectivamente una profundidad de pila inicial de cero, a pesar del 1 requerido en la parte superior de la pila. Como resultado, el 1 termina siendo agregado a sí mismo, y todo el triángulo se multiplica por 2. Al dividir el resultado final por 2 se obtiene la respuesta correcta.

Nitrodon
fuente