UNE numéro de Bell ( OEIS A000110 ) est le nombre de façons de partitionner un ensemble de n éléments (distincts) étiquetés. Le 0e numéro de Bell est défini comme 1.
Regardons quelques exemples (j'utilise des crochets pour désigner les sous-ensembles et les accolades pour les partitions):
1: {1}
2: {[1,2]}, {[1],[2]}
3: {[1,2,3]}, {[1,2],[3]}, {[1,3],[2]}, {[2,3],[1]}, {[1],[2],[3]}
Il y a plusieurs façons de calculer les numéros de Bell, et vous êtes libre d'utiliser n'importe lequel d'entre eux. Une façon sera décrite ici:
La façon la plus simple de calculer les nombres de Bell est d'utiliser un triangle numérique ressemblant au triangle de Pascal pour les coefficients binomiaux. Les numéros de Bell apparaissent sur les bords du triangle. En commençant par 1, chaque nouvelle ligne du triangle est construite en prenant la dernière entrée de la ligne précédente comme première entrée, puis en définissant chaque nouvelle entrée sur son voisin gauche plus son voisin supérieur gauche:
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
Vous pouvez utiliser l'indexation 0 ou l'indexation 1. Si vous utilisez l'indexation 0, une entrée de 3
devrait sortir 5
, mais devrait sortir 2
si vous utilisez l'indexation 1.
Votre programme doit fonctionner jusqu'au 15e numéro de Bell, produisant 1382958545
. En théorie, votre programme devrait être capable de gérer de plus grands nombres (en d'autres termes, ne codez pas en dur les solutions).
EDIT: vous n'êtes pas obligé de gérer une entrée de 0 (pour l'indexation 0) ou 1 (pour l'indexation 1) car elle n'est pas calculée par la méthode du triangle.
Cas de test (en supposant une indexation 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
Les réponses utilisant une méthode intégrée (comme BellB [n] dans le Wolfram Language) qui produisent directement des numéros de Bell ne seront pas compétitives.
Le code le plus court (en octets) gagne.
3
devrait sortir5
Elle sortirait15
, non? Et avec l'indexation 1, cela produirait5
3
devrait sortir2
. Que donnerait alors l'entrée1
avec l'indexation 1?Réponses:
Gelée , 9 octets
Cela utilise la formule
qui est fermé chaque fois que n <2 .
Essayez-le en ligne!
Comment ça fonctionne
la source
JavaScript (ES6), 47 octets
Le premier est indexé 0, le second est indexé 1.
la source
Haskell, 36 octets
Utilise la méthode du triangle, gère correctement la base 0, 0.
la source
R , 31 octets
utilise le numéro de Stirling du deuxième type et calcule ces nombres avec le package gmp ; lit à partir de stdin et renvoie la valeur sous forme de grand entier; échoue pour 0; 1 indexé.
la source
Mathematica, 24 octets
-13 octets de @Kelly Lowder!
la source
Sum[k^#/k!,{k,0,∞}]/E&
n'est que de 24 octetsGelée ,
141211 octetsEssayez-le en ligne!
N'a pas touché exactement les points forts de Jelly avec
une entrée dynamique dans¡
,Ṫ
modifiant toujours le tableau et l'absence d'atome en attente (un octet;@
ou inverséṭ
).la source
CJam (19 octets)
Démo en ligne
Dissection
la source
MATL , 14 octets
L'entrée est basée sur 0. Essayez-le en ligne!
Explication
Cela utilise la formule
où p F q ( a 1 , ..., a p ; b 1 , ..., b q ; x ) est la fonction hypergéométrique généralisée .
la source
Python , 42 octets
Essayez-le en ligne!
La formule récursive vient du placement d'
n
éléments dans des partitions. Pour chaque élément tour à tour, nous décidons de le placer:k
choixk
pour les éléments futursDans les deux cas, le nombre
n
d'éléments à placer diminue . Donc, nous avons la formule récursivef(n,k)=k*f(n-1,k)+f(n-1,k+1)
etf(0,k)=1
, avecf(n,0)
le n-ième numéro de Bell.la source
Python 2 , 91 octets
Essayez-le en ligne!
B (n) calculé comme une somme de nombres de Stirling du deuxième type.
la source
s
: puisque les appels récursifs diminuent toujoursn
et qu'il n'y a pas de division park
vous pouvez perdre le*k
dans le premier terme.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)
B
n'est pas récursive et qu'il s'agit de votre réponse finale, vous pouvez omettreB=
d' enregistrer 2 octetsMATLAB,
128103 octetsAssez explicite. L'omission d'un point-virgule à la fin d'une ligne imprime le résultat.
25 octets enregistrés grâce à Luis Mendo.
la source
R , 46 octets
Essayez-le en ligne!
la source
T
défautTRUE
(aka 1) à moins qu'il ne soit défini ailleursMATL ,
1918 octetsUtilise une entrée basée sur 0. Basé sur la relation de récurrence
Essayez-le en ligne!
la source
Ohm , 15 octets
Essayez-le en ligne!
Utilise le forumla de Dobinski (fonctionne même pour B (0) yay ).
Explication
la source
Python (79 octets)
Démo en ligne en en Python 2, mais elle fonctionne également en Python 3.
Cela construit le triangle d'Aitken en utilisant un lambda récursif pour une boucle de golf.
la source
Haskell , 35 octets
Essayez-le en ligne!
Formule expliquée dans ma réponse Python .
la source
J, 17 octets
Utilise la méthode de calcul du triangle.
Essayez-le en ligne!
Explication
la source
Python 3 , 78 octets
J'ai décidé d'essayer de suivre un itinéraire différent pour le calcul. Cela utilise la formule de Dobinski, indexée 0, ne fonctionne pas pour 0.
Essayez-le en ligne!
la source
f
n'est pas récursive, vous pouvez omettre lef=
et enregistrer 2 octetsPython 3 ,
6860 octetsConstruction récursive simple du triangle, mais il est extrêmement inefficace à des fins pratiques. Le calcul jusqu'au 15e numéro de Bell fait expirer TIO, mais cela fonctionne sur ma machine.
Cela utilise l'indexation 1 et renvoie
True
au lieu de 1.Essayez-le en ligne!
Merci à @FelipeNardiBatista pour avoir économisé 8 octets!
la source
PHP , 72 octets
fonction récursive indexée 1
Essayez-le en ligne!
PHP , 86 octets
0 indexé
Essayez-le en ligne!
PHP , 89 octets
fonction récursive indexée 0
Essayez-le en ligne!
la source
Alice , 22 octets
Essayez-le en ligne!
Cela utilise la méthode du triangle. Pour n = 0, cela calcule B (1) à la place, ce qui est commodément égal à B (0).
Explication
Il s'agit d'un modèle standard pour les programmes qui prennent des entrées en mode ordinal, les traitent en mode cardinal et produisent le résultat en mode ordinal. Un
1
a été ajouté au modèle pour mettre cette valeur sur la pile sous l'entrée.Le programme utilise la pile comme une file d'attente circulaire en expansion pour calculer chaque ligne du triangle. Au cours de chaque itération après la première, un zéro implicite sous la pile devient un zéro explicite.
La première itération suppose effectivement une profondeur de pile initiale de zéro, malgré le 1 requis en haut de la pile. En conséquence, le 1 finit par s'ajouter à lui-même et le triangle entier est multiplié par 2. La division du résultat final par 2 donne la bonne réponse.
la source
Pari / GP , 36 octets
Essayez-le en ligne!
la source