Bell numbers: Difference between revisions

{{trans|Python}}

 

[[BigInt]] tri

L(i) 0 .< n

print(‘The first ten rows of Bell's triangle:’)

L(i) 1..10

 

{{out}}

=={{header|Ada}}==

{{works with|GNAT|8.3.0}}

with Ada.Text_IO; use Ada.Text_IO;

procedure Main is

Bell_Numbers;

end Main;

{{out}}

<pre>

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

FI

OD

{{out}}

<pre>

 

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

integer function index(row, col);

integer row, col;

end;

end;

{{out}}

<pre>First fifteen Bell numbers:

=={{header|APL}}==

{{works with|Dyalog APL}}

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

⎕←'First 15 Bell numbers:'

⎕←'First 10 rows of Bell''s triangle:'

⎕←tr[⍳10;⍳10]

{{out}}

<pre>First 15 Bell numbers:

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

{{trans|C}}

110 LET M$ = CHR$ (13)

120 LET N = ROWS: GOSUB 500"BELLTRIANGLE"

580 LET BR = I:BC = J:BV = V + BV: GOSUB 400"SETBELL"

590 NEXT J,I

=={{header|Arturo}}==

 

{{trans|D}}

 

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

set get tri 1 0 1

 

loop 1..10 'i ->

 

{{out}}

 

=={{header|AutoHotkey}}==

Bell_triangle(maxRows){

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

return Trim(res, "`n")

}

MsgBox % Show_Bell_triangle(Bell_triangle(10))

{{out}}

<pre>1

=={{header|C}}==

{{trans|D}}

#include <stdlib.h>

 

free(bt);

return 0;

 

{{out}}

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

{{trans|D}}

using System.Numerics;

 

}

}

{{out}}

<pre>First fifteen and fiftieth Bell numbers:

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

 

}

return 0;

 

{{out}}

 

=={{header|CLU}}==

rep = array[int]

stream$putc(po, '\n')

end

{{out}}

<pre>The first 15 Bell numbers are:

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

===via Bell triangle===

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

(defun grow-triangle (triangle)

 

(format t "The first 10 rows of Bell triangle:~%")

{{out}}

<pre>B_0 (first Bell number) = 1

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

;; Final invocation

(loop for n in *numbers-to-print* do

{{out}}

<pre>B_0 (first Bell number) = 1

=={{header|Cowgol}}==

{{trans|C}}

 

typedef B is uint32;

i := i + 1;

print_nl();

 

{{out}}

=={{header|D}}==

{{trans|Go}}

import std.bigint;

import std.stdio : writeln, writefln;

writeln(bt[i]);

}

{{out}}

<pre>First fifteen and fiftieth Bell numbers:

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;

 

end;

end.

{{out}}

<pre>

 

=={{header|Elixir}}==

defmodule Bell do

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

IO.puts "THe first 10 rows of Bell's triangle:"

IO.inspect(Bell.triangle() |> Enum.take(10))

{{Out}}

<pre>

=={{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]

===The Task===

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

{{out}}

<pre>

[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 ""

{{out}}

<pre>

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

</pre>

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

{{out}}

<pre>

===via Aitken's array===

{{works with|Factor|0.98}}

 

: next-row ( prev -- next )

"First 15 Bell numbers:\n%[%d, %]\n\n50th: %d\n\n" printf

"First 10 rows of the Bell triangle:" print

{{out}}

<pre>

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 )

 

50 bells [ 15 head ] [ last ] bi

{{out}}

<pre>

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 )

 

50 [ bell ] { } map-integers [ 15 head ] [ last ] bi

{{out}}

As above.

 

=={{header|FreeBASIC}}==

 

#macro ncp(n, p)

next k

print n+1, bell(n+1)

 

=={{header|Go}}==

 

import (

fmt.Println(bt[i])

}

 

{{out}}

=={{header|Groovy}}==

{{trans|Java}}

private static class BellTriangle {

private List<Integer> arr

}

}

{{out}}

<pre>First fifteen Bell numbers:

=={{header|Haskell}}==

 

bellTri =

let f xs = (last xs, xs)

mapM_ print (take 15 bell)

putStrLn "\n50th Bell number:"

 

{{out}}

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:

 

=={{header|J}}==

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

 

{:>bell^:49<1x

185724268771078270438257767181908917499221852770

 

=={{header|Java}}==

{{trans|Kotlin}}

import java.util.List;

 

}

}

{{out}}

<pre>First fifteen Bell numbers:

=={{header|jq}}==

{{trans|Julia}}

def bell:

. as $n

 

# The task

{{out}}

For displaying the results, we will first use gojq, the Go implementation of jq, as it supports unbounded-precision integer arithmetic.

=={{header|Julia}}==

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

bellnum(n)

Compute the ``n``th Bell number.

for i in 1:50

println(bellnum(i))

{{out}}

<pre>

=={{header|Kotlin}}==

{{trans|C}}

private val arr: Array<Int>

 

println()

}

{{out}}

<pre>First fifteen Bell numbers:

 

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.

// Rest of array goes here

// end

{{out}}

<pre>

 

=={{header|Lua}}==

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

 

for i = 1, 10 do

print("[ " .. table.concat(tri[i],", ") .. " ]")

{{out}}

<pre>First 15 and 25th Bell numbers:

=={{header|Maple}}==

 

option remember;

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

# [1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570,

# 4213597, 27644437, 190899322, 1382958545, 10480142147,

 

=={{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]

 

6097, 7432, 9089, 11155, 13744, 17007, 21147}, {21147, 25287, 30304,

36401, 43833, 52922, 64077, 77821, 94828, 115975}}

 

=={{header|Nim}}==

===Using Recurrence relation===

 

iterator b(): int =

inc i

if i > Limit:

 

{{out}}

 

===Using Bell triangle===

## Iterator yielding the bell numbers.

var row = @[1]

echo line

if i == 10:

 

{{out}}

=={{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));

listput(bell,q));bell}

'''Output:'''

<nowiki>List([1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, 51724158235372, 474869816156751, 4506715738447323, 44152005855084346, 445958869294805289, 4638590332229999353, 49631246523618756274, 545717047936059989389, 6160539404599934652455, 71339801938860275191172, 846749014511809332450147, 10293358946226376485095653, 128064670049908713818925644, 1629595892846007606764728147, 21195039388640360462388656799, 281600203019560266563340426570, 3819714729894818339975525681317, 52868366208550447901945575624941, 746289892095625330523099540639146, 10738823330774692832768857986425209, 157450588391204931289324344702531067, 2351152507740617628200694077243788988, 35742549198872617291353508656626642567, 552950118797165484321714693280737767385, 8701963427387055089023600531855797148876, 139258505266263669602347053993654079693415, 2265418219334494002928484444705392276158355, 37450059502461511196505342096431510120174682, 628919796303118415420210454071849537746015761, 10726137154573358400342215518590002633917247281, 185724268771078270438257767181908917499221852770])</nowiki>

{{Works with|Free Pascal}}

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

{$Ifdef FPC}

{$optimization on,all}

BellNumbersUint64(True);BellNumbersUint64(False);

BellNumbersMPInteger;

{{out}}

<pre style="height:180px">

=={{header|Perl}}==

{{trans|Raku}}

use warnings;

use feature 'say';

 

say "\nFirst ten rows of Aitken's array:";

{{out}}

<pre>First fifteen and fiftieth Bell numbers:

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

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bt</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])})</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre>

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

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

B50=b(50),

println(B50[1..18]),

end,

R := R ++ [A[1]]

 

{{out}}

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

{{trans|D}}

Tri = tri(50),

foreach(I in 1..10)

Tri[I,J] := Tri[I,J-1] + Tri[I-1,J-1]

end

 

{{out}}

 

{{trans|Prolog}}

bell(49, Bell),

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

print_bell_row([Number|Numbers]):-

printf("%w ", Number),

 

{{out}}

 

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

#/\ ((#~ B[I] #= 1) #=> (X[I] #!= T))

end,

 

{{out}}

 

=={{header|PicoLisp}}==

(make

(setq L (link (list 1)))

(prinl "First ten rows:")

(for N 10

{{out}}

<pre>

=={{header|Prolog}}==

{{works with|SWI Prolog}}

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

 

writef('\n50th Bell number: %w\n', [Number]),

writef('\nFirst 10 rows of Bell triangle:\n'),

 

{{out}}

{{trans|D}}

{{Works with|Python|2.7}}

tri = [None] * n

for i in xrange(n):

print bt[i]

 

{{out}}

<pre>First fifteen and fiftieth Bell numbers:

{{Trans|Haskell}}

{{Works with|Python|3.7}}

 

from itertools import accumulate, chain, islice

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>First fifteen Bell numbers:

=={{header|Quackery}}==

 

rot 1 - times

[ dup -1 peek nested

cr cr

say "First ten rows of Bell's triangle:" cr

 

{{out}}

=={{header|Racket}}==

 

 

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

(map bell-number (range 15))

(bell-number 50)

 

{{out}}

{{works with|Rakudo|2019.03}}

 

my @c = @b.tail;

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

 

say "\nFirst ten rows of Aitken's array:";

{{out}}

<pre>First fifteen and fiftieth Bell numbers:

{{works with|Rakudo|2019.03}}

 

 

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

 

{{out}}

<pre>(1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322)

{{works with|Rakudo|2019.03}}

 

(1,),

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

my @bell = @Stirling_numbers_of_the_second_kind.map: *.sum;

 

{{out}}

<pre>(1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322)

 

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.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

fact: procedure expose !.; parse arg x; if !.x\==. then return !.x; != 1

{{out|output|text=&nbsp; when using the internal default inputs of: &nbsp; &nbsp; <tt> 0 &nbsp; 14 </tt>}}

<pre>

=={{header|Ruby}}==

{{trans|D}}

tri = Array.new(n)

for i in 0 .. n - 1 do

end

 

{{out}}

<pre>First fifteen and fiftieth Bell numbers:

{{trans|D}}

{{libheader|num|0.2}}

 

fn main() {

tri

}

 

{{out}}

=={{header|Scala}}==

{{trans|Java}}

 

object BellNumbers {

}

}

{{out}}

<pre>First fifteen Bell numbers:

=={{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).

(eleloop (cdr rowlist))))

(newline)

{{out}}

<pre>The Bell numbers:

=={{header|Sidef}}==

Built-in:

 

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

 

Via Aitken's array (optimized for space):

 

var acc = []

var B = bell_numbers(50)

say "The first 15 Bell numbers: #{B.first(15).join(', ')}"

{{out}}

<pre>

 

Aitken's array:

 

var A = [1]

}

 

{{out}}

<pre>

 

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

for n in (^10) {

say (0..n -> map{|k| A(n, k) })

 

(same output as above)

{{trans|Kotlin}}

 

@usableFromInline

var arr: [T]

 

print()

 

{{out}}

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

{{trans|C#}}

Imports System.Runtime.CompilerServices

 

End Sub

 

{{out}}

<pre>First fifteen Bell numbers:

=={{header|Vlang}}==

{{trans|Go}}

 

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

println(bt[i])

}

 

{{out}}

{{trans|Go}}

{{libheader|Wren-fmt}}

import "/fmt" for Fmt

 

Fmt.print("$2d: $,i", 50, bt[50][0])

System.print("\nThe first ten rows of Bell's triangle:")

 

{{out}}

 

=={{header|zkl}}==

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

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

wantRow and row or row[-1]

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

{{out}}

<pre>

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

</pre>

{{out}}

<pre>

</pre>

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

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

{{out}}

<pre>