Bell numbers: Difference between revisions
m
syntax highlighting fixup automation
(Applesoft BASIC) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 35:
{{trans|Python}}
<
[[BigInt]] tri
L(i) 0 .< n
Line 54:
print(‘The first ten rows of Bell's triangle:’)
L(i) 1..10
print(bt[i])</
{{out}}
Line 91:
=={{header|Ada}}==
{{works with|GNAT|8.3.0}}
<
with Ada.Text_IO; use Ada.Text_IO;
procedure Main is
Line 151:
Bell_Numbers;
end Main;
</syntaxhighlight>
{{out}}
<pre>
Line 188:
{{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 ) );
Line 208:
FI
OD
END</
{{out}}
<pre>
Line 231:
=={{header|ALGOL-M}}==
<
integer function index(row, col);
integer row, col;
Line 266:
end;
end;
end</
{{out}}
<pre>First fifteen Bell numbers:
Line 299:
=={{header|APL}}==
{{works with|Dyalog APL}}
<
tr←↑(⊢,(⊂⊃∘⌽+0,+\)∘⊃∘⌽)⍣14⊢,⊂,1
⎕←'First 15 Bell numbers:'
Line 305:
⎕←'First 10 rows of Bell''s triangle:'
⎕←tr[⍳10;⍳10]
}</
{{out}}
<pre>First 15 Bell numbers:
Line 323:
=={{header|Applesoft BASIC}}==
{{trans|C}}
<
110 LET M$ = CHR$ (13)
120 LET N = ROWS: GOSUB 500"BELLTRIANGLE"
Line 363:
580 LET BR = I:BC = J:BV = V + BV: GOSUB 400"SETBELL"
590 NEXT J,I
600 RETURN</
=={{header|Arturo}}==
{{trans|D}}
<
tri: map 0..n-1 'x [ map 0..n 'y -> 0 ]
set get tri 1 0 1
Line 388:
loop 1..10 'i ->
print filter bt\[i] => zero?</
{{out}}
Line 422:
=={{header|AutoHotkey}}==
<
Bell_triangle(maxRows){
row := 1, col := 1, Arr := []
Line 453:
return Trim(res, "`n")
}
;-----------------------------------</
Examples:<
MsgBox % Show_Bell_triangle(Bell_triangle(10))
return</
{{out}}
<pre>1
Line 487:
=={{header|C}}==
{{trans|D}}
<
#include <stdlib.h>
Line 543:
free(bt);
return 0;
}</
{{out}}
Line 577:
=={{header|C sharp|C#}}==
{{trans|D}}
<
using System.Numerics;
Line 631:
}
}
}</
{{out}}
<pre>First fifteen and fiftieth Bell numbers:
Line 666:
{{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>
Line 716:
}
return 0;
}</
{{out}}
Line 753:
=={{header|CLU}}==
<
rep = array[int]
Line 798:
stream$putc(po, '\n')
end
end start_up</
{{out}}
<pre>The first 15 Bell numbers are:
Line 831:
=={{header|Common Lisp}}==
===via Bell triangle===
<
;; triangle's row; the last row is at the head of the list.
(defun grow-triangle (triangle)
Line 891:
(format t "The first 10 rows of Bell triangle:~%")
(print-bell-triangle (make-triangle 10))</
{{out}}
<pre>B_0 (first Bell number) = 1
Line 930:
===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
Line 972:
;; Final invocation
(loop for n in *numbers-to-print* do
(print-bell-number n (bell n)))</
{{out}}
<pre>B_0 (first Bell number) = 1
Line 999:
=={{header|Cowgol}}==
{{trans|C}}
<
typedef B is uint32;
Line 1,066:
i := i + 1;
print_nl();
end loop;</
{{out}}
Line 1,101:
=={{header|D}}==
{{trans|Go}}
<
import std.bigint;
import std.stdio : writeln, writefln;
Line 1,133:
writeln(bt[i]);
}
}</
{{out}}
<pre>First fifteen and fiftieth Bell numbers:
Line 1,169:
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;
Line 1,205:
end;
end.
</syntaxhighlight>
{{out}}
<pre>
Line 1,237:
=={{header|Elixir}}==
<
defmodule Bell do
def triangle(), do: Stream.iterate([1], fn l -> bell_row l, [List.last l] end)
Line 1,254:
IO.puts "THe first 10 rows of Bell's triangle:"
IO.inspect(Bell.triangle() |> Enum.take(10))
</syntaxhighlight>
{{Out}}
<pre>
Line 1,279:
=={{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>
{{out}}
<pre>
Line 1,300:
[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>
{{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))
</syntaxhighlight>
{{out}}
<pre>
Line 1,318:
===via Aitken's array===
{{works with|Factor|0.98}}
<
: next-row ( prev -- next )
Line 1,330:
"First 15 Bell numbers:\n%[%d, %]\n\n50th: %d\n\n" printf
"First 10 rows of the Bell triangle:" print
10 aitken [ "%[%d, %]\n" printf ] each</
{{out}}
<pre>
Line 1,353:
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 )
Line 1,362:
50 bells [ 15 head ] [ last ] bi
"First 15 Bell numbers:\n%[%d, %]\n\n50th: %d\n" printf</
{{out}}
<pre>
Line 1,373:
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 )
Line 1,379:
50 [ bell ] { } map-integers [ 15 head ] [ last ] bi
"First 15 Bell numbers:\n%[%d, %]\n\n50th: %d\n" printf</
{{out}}
As above.
=={{header|FreeBASIC}}==
<
#macro ncp(n, p)
Line 1,405:
next k
print n+1, bell(n+1)
next n</
=={{header|Go}}==
<
import (
Line 1,444:
fmt.Println(bt[i])
}
}</
{{out}}
Line 1,481:
=={{header|Groovy}}==
{{trans|Java}}
<
private static class BellTriangle {
private List<Integer> arr
Line 1,538:
}
}
}</
{{out}}
<pre>First fifteen Bell numbers:
Line 1,569:
=={{header|Haskell}}==
<
bellTri =
let f xs = (last xs, xs)
Line 1,584:
mapM_ print (take 15 bell)
putStrLn "\n50th Bell number:"
print (bell !! 49)</
{{out}}
Line 1,621:
And, of course, in terms of ''Control.Arrow'' or ''Control.Applicative'', the triangle function could also be written as:
<
bellTri :: [[Integer]]
bellTri = map snd (iterate ((last &&& id) . uncurry (scanl (+))) (1,[1]))</
or:
<
bellTri :: [[Integer]]
bellTri = map snd (iterate ((liftA2 (,) last id) . uncurry (scanl (+))) (1,[1]))</
or, as an applicative without the need for an import:
<
bellTri = map snd (iterate (((,) . last <*> id) . uncurry (scanl (+))) (1, [1]))</
=={{header|J}}==
<syntaxhighlight lang=text>
bell=: ([: +/\ (,~ {:))&.>@:{:
Line 1,659:
{:>bell^:49<1x
185724268771078270438257767181908917499221852770
</syntaxhighlight>
=={{header|Java}}==
{{trans|Kotlin}}
<
import java.util.List;
Line 1,723:
}
}
}</
{{out}}
<pre>First fifteen Bell numbers:
Line 1,754:
=={{header|jq}}==
{{trans|Julia}}
<
def bell:
. as $n
Line 1,769:
# The task
range(1;51) | bell</
{{out}}
For displaying the results, we will first use gojq, the Go implementation of jq, as it supports unbounded-precision integer arithmetic.
Line 1,799:
=={{header|Julia}}==
Source: Combinatorics at https://github.com/JuliaMath/Combinatorics.jl/blob/master/src/numbers.jl
<
bellnum(n)
Compute the ``n``th Bell number.
Line 1,822:
for i in 1:50
println(bellnum(i))
end</
{{out}}
<pre>
Line 1,879:
=={{header|Kotlin}}==
{{trans|C}}
<
private val arr: Array<Int>
Line 1,930:
println()
}
}</
{{out}}
<pre>First fifteen Bell numbers:
Line 1,963:
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.
Line 2,037:
// Rest of array goes here
// end
</syntaxhighlight>
{{out}}
<pre>
Line 2,052:
=={{header|Lua}}==
<
-- db 6/11/2020 (to replace missing original)
Line 2,080:
for i = 1, 10 do
print("[ " .. table.concat(tri[i],", ") .. " ]")
end</
{{out}}
<pre>First 15 and 25th Bell numbers:
Line 2,114:
=={{header|Maple}}==
<
option remember;
add(binomial(n-1,k)*bell1(k),k=0..n-1)
Line 2,129:
# [1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570,
# 4213597, 27644437, 190899322, 1382958545, 10480142147,
# 82864869804, 682076806159, 5832742205057, 51724158235372]</
=={{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]];
</syntaxhighlight>
'''Output:'''
<
In[51]:= Array[BellNumber, 25]
Line 2,154:
6097, 7432, 9089, 11155, 13744, 17007, 21147}, {21147, 25287, 30304,
36401, 43833, 52922, 64077, 77821, 94828, 115975}}
</syntaxhighlight>
=={{header|Nim}}==
===Using Recurrence relation===
<
iterator b(): int =
Line 2,185:
inc i
if i > Limit:
break</
{{out}}
Line 2,217:
===Using Bell triangle===
<
## Iterator yielding the bell numbers.
var row = @[1]
Line 2,267:
echo line
if i == 10:
break</
{{out}}
Line 2,311:
=={{header|PARIGP}}==
From the code at OEIS A000110,
<syntaxhighlight lang=text>
genit(maxx=50)={bell=List();
for(n=0,maxx,q=sum(k=0,n,stirling(n,k,2));
listput(bell,q));bell}
END</
'''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>
Line 2,322:
{{Works with|Free Pascal}}
Using bell's triangle. TIO.RUN up to 5000.See talk for more.
<
{$Ifdef FPC}
{$optimization on,all}
Line 2,442:
BellNumbersUint64(True);BellNumbersUint64(False);
BellNumbersMPInteger;
END.</
{{out}}
<pre style="height:180px">
Line 2,544:
=={{header|Perl}}==
{{trans|Raku}}
<
use warnings;
use feature 'say';
Line 2,565:
say "\nFirst ten rows of Aitken's array:";
printf '%-7d'x@{$Aitkens[$_]}."\n", @{$Aitkens[$_]} for 0..9;</
{{out}}
<pre>First fifteen and fiftieth Bell numbers:
Line 2,601:
{{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>
Line 2,631:
<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>
Line 2,654:
'''First 18 Bell numbers and b(50).'''
(Port of the Sage solution at the OEIS A000110 page.)
<
B50=b(50),
println(B50[1..18]),
Line 2,671:
end,
R := R ++ [A[1]]
end.</
{{out}}
Line 2,679:
'''Bell's Triangle (and the 50th Bell number)'''
{{trans|D}}
<
Tri = tri(50),
foreach(I in 1..10)
Line 2,701:
Tri[I,J] := Tri[I,J-1] + Tri[I-1,J-1]
end
end.</
{{out}}
Line 2,718:
{{trans|Prolog}}
<
bell(49, Bell),
printf("First 15 Bell numbers:\n"),
Line 2,762:
print_bell_row([Number|Numbers]):-
printf("%w ", Number),
print_bell_row(Numbers).</
{{out}}
Line 2,813:
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 =>
Line 2,858:
#/\ ((#~ B[I] #= 1) #=> (X[I] #!= T))
end,
B[1] #= 0.</
{{out}}
Line 2,886:
=={{header|PicoLisp}}==
<
(make
(setq L (link (list 1)))
Line 2,903:
(prinl "First ten rows:")
(for N 10
(println (get L N)) )</
{{out}}
<pre>
Line 2,938:
=={{header|Prolog}}==
{{works with|SWI Prolog}}
<
bell(N, Bell, [], _).
Line 2,982:
writef('\n50th Bell number: %w\n', [Number]),
writef('\nFirst 10 rows of Bell triangle:\n'),
print_bell_rows(Bell, 10).</
{{out}}
Line 3,022:
{{trans|D}}
{{Works with|Python|2.7}}
<
tri = [None] * n
for i in xrange(n):
Line 3,044:
print bt[i]
main()</
{{out}}
<pre>First fifteen and fiftieth Bell numbers:
Line 3,079:
{{Trans|Haskell}}
{{Works with|Python|3.7}}
<
from itertools import accumulate, chain, islice
Line 3,276:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>First fifteen Bell numbers:
Line 3,312:
=={{header|Quackery}}==
<
rot 1 - times
[ dup -1 peek nested
Line 3,330:
cr cr
say "First ten rows of Bell's triangle:" cr
10 bell's-triangle witheach [ echo cr ]</
{{out}}
Line 3,355:
=={{header|Racket}}==
<
(define (build-bell-row previous-row)
Line 3,380:
(map bell-number (range 15))
(bell-number 50)
(bell-triangle 10))</
{{out}}
Line 3,404:
{{works with|Rakudo|2019.03}}
<syntaxhighlight lang=raku
my @c = @b.tail;
@c.push: @b[$_] + @c[$_] for ^@b;
Line 3,416:
say "\nFirst ten rows of Aitken's array:";
.say for @Aitkens-array[^10];</
{{out}}
<pre>First fifteen and fiftieth Bell numbers:
Line 3,451:
{{works with|Rakudo|2019.03}}
<syntaxhighlight lang=raku
my @bell = 1, -> *@s { [+] @s »*« @s.keys.map: { binomial(@s-1, $_) } } … *;
.say for @bell[^15], @bell[50 - 1];</
{{out}}
<pre>(1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322)
Line 3,463:
{{works with|Rakudo|2019.03}}
<syntaxhighlight lang=raku
(1,),
{ (0, |@^last) »+« (|(@^last »*« @^last.keys), 0) } … *
Line 3,469:
my @bell = @Stirling_numbers_of_the_second_kind.map: *.sum;
.say for @bell.head(15), @bell[50 - 1];</
{{out}}
<pre>(1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322)
Line 3,483:
Also, see this task's [https://rosettacode.org/wiki/Talk:Bell_numbers#size_of_Bell_numbers ''discussion''] 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.*/
Line 3,506:
/*──────────────────────────────────────────────────────────────────────────────────────*/
fact: procedure expose !.; parse arg x; if !.x\==. then return !.x; != 1
do f=2 for x-1; != ! * f; end; !.x= !; return !</
{{out|output|text= when using the internal default inputs of: <tt> 0 14 </tt>}}
<pre>
Line 3,532:
=={{header|Ruby}}==
{{trans|D}}
<
tri = Array.new(n)
for i in 0 .. n - 1 do
Line 3,565:
end
main()</
{{out}}
<pre>First fifteen and fiftieth Bell numbers:
Line 3,600:
{{trans|D}}
{{libheader|num|0.2}}
<
fn main() {
Line 3,631:
tri
}
</syntaxhighlight>
{{out}}
Line 3,655:
=={{header|Scala}}==
{{trans|Java}}
<
object BellNumbers {
Line 3,714:
}
}
}</
{{out}}
<pre>First fifteen Bell numbers:
Line 3,744:
=={{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).
Line 3,791:
(eleloop (cdr rowlist))))
(newline)
(rowloop (cdr triangle))))</
{{out}}
<pre>The Bell numbers:
Line 3,832:
=={{header|Sidef}}==
Built-in:
<
Formula as a sum of Stirling numbers of the second kind:
<
Via Aitken's array (optimized for space):
<
var acc = []
Line 3,854:
var B = bell_numbers(50)
say "The first 15 Bell numbers: #{B.first(15).join(', ')}"
say "The fiftieth Bell number : #{B[50-1]}"</
{{out}}
<pre>
Line 3,862:
Aitken's array:
<
var A = [1]
Line 3,871:
}
aitken_array(10).each { .say }</
{{out}}
<pre>
Line 3,887:
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) }
Line 3,893:
for n in (^10) {
say (0..n -> map{|k| A(n, k) })
}</
(same output as above)
Line 3,901:
{{trans|Kotlin}}
<
@usableFromInline
var arr: [T]
Line 3,943:
print()
}</
{{out}}
Line 3,976:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Imports System.Runtime.CompilerServices
Line 4,029:
End Sub
End Module</
{{out}}
<pre>First fifteen Bell numbers:
Line 4,063:
=={{header|Vlang}}==
{{trans|Go}}
<
fn bell_triangle(n int) [][]big.Integer {
Line 4,094:
println(bt[i])
}
}</
{{out}}
Line 4,132:
{{trans|Go}}
{{libheader|Wren-fmt}}
<
import "/fmt" for Fmt
Line 4,156:
Fmt.print("$2d: $,i", 50, bt[50][0])
System.print("\nThe first ten rows of Bell's triangle:")
for (i in 1..10) Fmt.print("$,7i", bt[i])</
{{out}}
Line 4,192:
=={{header|zkl}}==
<
Walker.zero().tweak('wrap(row){
row.insert(0,row[-1]);
Line 4,198:
wantRow and row or row[-1]
}.fp(List(start))).push(start,start);
}</
<
bellTriangleW().walk(15).println();</
{{out}}
<pre>
Line 4,206:
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()) }</
{{out}}
<pre>
Line 4,224:
</pre>
{{libheader|GMP}} GNU Multiple Precision Arithmetic Library
<
var [const] BI=Import("zklBigNum"); // libGMP
bellTriangleW(BI(1)).drop(50).value.println();</
{{out}}
<pre>
|