Bell numbers: Difference between revisions

{{trans|Python}}

[[BigInt]] tri

L(i) 0 .< n

=={{header|Ada}}==

{{works with|GNAT|8.3.0}}

with Ada.Text_IO; use Ada.Text_IO;

procedure Main is

{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}

Uses Algol 68G's LONG LONG INT to calculate the numbers up to 50. Calculates the numbers using the triangle algorithm but without storing the triangle as a whole - each line of the triangle replaces the previous one.

PROC show bell = ( INT n, LONG LONG INT bell number )VOID:

print( ( whole( n, -2 ), ": ", whole( bell number, 0 ), newline ) );

=={{header|ALGOL-M}}==

integer function index(row, col);

integer row, col;

=={{header|APL}}==

{{works with|Dyalog APL}}

tr←↑(⊢,(⊂⊃∘⌽+0,+\)∘⊃∘⌽)⍣14⊢,⊂,1

⎕←'First 15 Bell numbers:'

=={{header|Applesoft BASIC}}==

{{trans|C}}

110 LET M$ = CHR$ (13)

120 LET N = ROWS: GOSUB 500"BELLTRIANGLE"

{{trans|D}}

tri: map 0..n-1 'x [ map 0..n 'y -> 0 ]

set get tri 1 0 1

=={{header|AutoHotkey}}==

Bell_triangle(maxRows){

row := 1, col := 1, Arr := []

}

;-----------------------------------</syntaxhighlight>

MsgBox % Show_Bell_triangle(Bell_triangle(10))

return</syntaxhighlight>

=={{header|C}}==

{{trans|D}}

#include <stdlib.h>

=={{header|C sharp|C#}}==

{{trans|D}}

using System.Numerics;

{{libheader|Boost}}

Requires C++14 or later. If HAVE_BOOST is defined, we use the cpp_int class from Boost so we can display the 50th Bell number, as shown in the output section below.

#include <vector>

=={{header|CLU}}==

rep = array[int]

=={{header|Common Lisp}}==

===via Bell triangle===

;; triangle's row; the last row is at the head of the list.

(defun grow-triangle (triangle)

===via Stirling numbers of the second kind===

This solution's algorithm is substantially slower than the algorithm based on the Bell triangle, because of the many nested loops.

;; Compute the factorial

=={{header|Cowgol}}==

{{trans|C}}

typedef B is uint32;

=={{header|D}}==

{{trans|Go}}

import std.bigint;

import std.stdio : writeln, writefln;

It shows a way of calculating Bell numbers without using a triangle.

Output numbering is as in the statement of the task, namely B_0 = 1, B_1 = 1, B_2 = 2, ....

program BellNumbers;

=={{header|Elixir}}==

defmodule Bell do

def triangle(), do: Stream.iterate([1], fn l -> bell_row l, [List.last l] end)

=={{header|F_Sharp|F#}}==

===The function===

// Generate bell triangle. Nigel Galloway: July 6th., 2019

let bell=Seq.unfold(fun g->Some(g,List.scan(+) (List.last g) g))[1I]

</syntaxhighlight>

===The Task===

bell|>Seq.take 10|>Seq.iter(printfn "%A")

</syntaxhighlight>

[21147; 25287; 30304; 36401; 43833; 52922; 64077; 77821; 94828; 115975]

</pre>

bell|>Seq.take 15|>Seq.iter(fun n->printf "%A " (List.head n));printfn ""

</syntaxhighlight>

1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322

</pre>

printfn "%A" (Seq.head (Seq.item 49 bell))

</syntaxhighlight>

===via Aitken's array===

{{works with|Factor|0.98}}

: next-row ( prev -- next )

This solution makes use of a [https://en.wikipedia.org/wiki/Bell_number#Summation_formulas recurrence relation] involving binomial coefficients.

{{works with|Factor|0.98}}

: next-bell ( seq -- n )

This solution defines Bell numbers in terms of [https://en.wikipedia.org/wiki/Bell_number#Summation_formulas sums of Stirling numbers of the second kind].

{{works with|Factor|0.99 development release 2019-07-10}}

: bell ( m -- n )

=={{header|FreeBASIC}}==

#macro ncp(n, p)

=={{header|Go}}==

import (

=={{header|Groovy}}==

{{trans|Java}}

private static class BellTriangle {

private List<Integer> arr

=={{header|Haskell}}==

bellTri =

let f xs = (last xs, xs)

And, of course, in terms of ''Control.Arrow'' or ''Control.Applicative'', the triangle function could also be written as:

bellTri :: [[Integer]]

or:

bellTri :: [[Integer]]

or, as an applicative without the need for an import:

bellTri = map snd (iterate (((,) . last <*> id) . uncurry (scanl (+))) (1, [1]))</syntaxhighlight>

=={{header|J}}==

bell=: ([: +/\ (,~ {:))&.>@:{:

=={{header|Java}}==

{{trans|Kotlin}}

import java.util.List;

=={{header|jq}}==

{{trans|Julia}}

def bell:

. as $n

=={{header|Julia}}==

Source: Combinatorics at https://github.com/JuliaMath/Combinatorics.jl/blob/master/src/numbers.jl

bellnum(n)

Compute the ``n``th Bell number.

=={{header|Kotlin}}==

{{trans|C}}

private val arr: Array<Int>

In order to handle arrays, a program for the LMC has to modify its own code. This practice is usually frowned on nowadays, but was standard on very early real-life computers, such as EDSAC.

// Little Man Computer, for Rosetta Code.

// Calculate Bell numbers, using a 1-dimensional array and addition.

=={{header|Lua}}==

-- db 6/11/2020 (to replace missing original)

=={{header|Maple}}==

option remember;

add(binomial(n-1,k)*bell1(k),k=0..n-1)

=={{header|Mathematica}} / {{header|Wolfram Language}}==

'''Function definition:'''

BellTriangle[n_Integer?Positive] := NestList[Accumulate[# /. {a___, b_} :> {b, a, b}] &, {1}, n - 1];

BellNumber[n_Integer] := BellTriangle[n][[n, 1]];

'''Output:'''

In[51]:= Array[BellNumber, 25]

=={{header|Nim}}==

===Using Recurrence relation===

iterator b(): int =

===Using Bell triangle===

## Iterator yielding the bell numbers.

var row = @[1]

=={{header|PARIGP}}==

From the code at OEIS A000110,

genit(maxx=50)={bell=List();

for(n=0,maxx,q=sum(k=0,n,stirling(n,k,2));

{{Works with|Free Pascal}}

Using bell's triangle. TIO.RUN up to 5000.See talk for more.

{$Ifdef FPC}

{$optimization on,all}

=={{header|Perl}}==

{{trans|Raku}}

use warnings;

use feature 'say';

{{libheader|Phix/mpfr}}

Started out as a translation of Go, but the main routine has now been completely replaced.

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>

'''First 18 Bell numbers and b(50).'''

(Port of the Sage solution at the OEIS A000110 page.)

B50=b(50),

println(B50[1..18]),

'''Bell's Triangle (and the 50th Bell number)'''

{{trans|D}}

Tri = tri(50),

foreach(I in 1..10)

{{trans|Prolog}}

bell(49, Bell),

printf("First 15 Bell numbers:\n"),

The symmetry constraint <code>value_precede_chain/2</code> ensures that a value N+1 is not placed in the list (X) before all the values 1..N has been placed ("seen") in the list. This handles the symmetry that the two sets {1,2} and {2,1} are to be considered the same.

main =>

=={{header|PicoLisp}}==

(make

(setq L (link (list 1)))

=={{header|Prolog}}==

{{works with|SWI Prolog}}

bell(N, Bell, [], _).

{{trans|D}}

{{Works with|Python|2.7}}

tri = [None] * n

for i in xrange(n):

{{Trans|Haskell}}

{{Works with|Python|3.7}}

from itertools import accumulate, chain, islice

=={{header|Quackery}}==

rot 1 - times

[ dup -1 peek nested

=={{header|Racket}}==

(define (build-bell-row previous-row)

{{works with|Rakudo|2019.03}}

my @c = @b.tail;

@c.push: @b[$_] + @c[$_] for ^@b;

{{works with|Rakudo|2019.03}}

my @bell = 1, -> *@s { [+] @s »*« @s.keys.map: { binomial(@s-1, $_) } } … *;

{{works with|Rakudo|2019.03}}

(1,),

{ (0, |@^last) »+« (|(@^last »*« @^last.keys), 0) } … *

Also, see this task's &nbsp; [https://rosettacode.org/wiki/Talk:Bell_numbers#size_of_Bell_numbers ''discussion''] &nbsp; to view how the sizes of Bell numbers increase in relation to its index.

parse arg LO HI . /*obtain optional arguments from the CL*/

if LO=='' & HI=="" then do; LO=0; HI=14; end /*Not specified? Then use the default.*/

=={{header|Ruby}}==

{{trans|D}}

tri = Array.new(n)

for i in 0 .. n - 1 do

{{trans|D}}

{{libheader|num|0.2}}

fn main() {

=={{header|Scala}}==

{{trans|Java}}

object BellNumbers {

=={{header|Scheme}}==

{{works with|Chez Scheme}}

; extend (in situ) the current row to be a complete row of the Bell triangle.

; Return the final value in the extended row (for use in computing the following row).

=={{header|Sidef}}==

Built-in:

Formula as a sum of Stirling numbers of the second kind:

Via Aitken's array (optimized for space):

var acc = []

Aitken's array:

var A = [1]

Aitken's array (recursive definition):

func A(n, (0)) { A(n-1, n-1) }

func A(n, k) is cached { A(n, k-1) + A(n-1, k-1) }

{{trans|Kotlin}}

@usableFromInline

var arr: [T]

=={{header|Visual Basic .NET}}==

{{trans|C#}}

Imports System.Runtime.CompilerServices

=={{header|Vlang}}==

{{trans|Go}}

fn bell_triangle(n int) [][]big.Integer {

{{trans|Go}}

{{libheader|Wren-fmt}}

import "/fmt" for Fmt

=={{header|zkl}}==

Walker.zero().tweak('wrap(row){

row.insert(0,row[-1]);

}.fp(List(start))).push(start,start);

}</syntaxhighlight>

bellTriangleW().walk(15).println();</syntaxhighlight>

{{out}}

L(1,1,2,5,15,52,203,877,4140,21147,115975,678570,4213597,27644437,190899322)

</pre>

bt:=bellTriangleW(1,True); do(11){ println(bt.next()) }</syntaxhighlight>

{{out}}

</pre>

{{libheader|GMP}} GNU Multiple Precision Arithmetic Library

var [const] BI=Import("zklBigNum"); // libGMP

bellTriangleW(BI(1)).drop(50).value.println();</syntaxhighlight>