Rosetta Code

Stirling numbers of the second kind: Difference between revisions

Page Discussion

Stirling numbers of the second kind (view source)

Revision as of 14:35, 25 March 2024

3,685 bytes added ,  1 month ago
added RPL
(added RPL)
 
(11 intermediate revisions by 5 users not shown)
Line 39:
{{trans|Python}}
 
<langsyntaxhighlight lang="11l">[(Int, Int) = BigInt] computed
 
F sterling2(n, k)
Line 77:
E
print("#.\n(#. digits, k = #.)\n".format(previous, String(previous).len, k - 1))
L.break</langsyntaxhighlight>
 
{{out}}
Line 104:
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
Uses the LONG LONG INT mode of Algol 68g which allows large precision integers. As the default precision of LONG LONG INT is too small, the precision is specified via a pragmatic comment.
<langsyntaxhighlight lang="algol68">BEGIN
BEGIN # show some Stirling numbers of the second kind #
 
# specify the precision of LONG LONG INT, somewhat under 160 digits are #
Line 132:
print( ( "Stirling numbers of the second kind:", newline ) );
print( ( " k" ) );
FOR k FROM 0 TO max stirling DO print( ( whole( k, -108 ) ) ) OD;
print( ( newline, " n", newline ) );
FOR n FROM 0 TO max stirling DO
print( ( whole( n, -2 ) ) );
FOR k FROM 0 TO n DO
print( ( whole( s2[ n, k ], -108 ) ) )
OD;
print( ( newline ) )
Line 153:
print( ( whole( max 100, 0 ), newline ) )
END
END</lang>
</syntaxhighlight>
{{out}}
<pre>
Stirling numbers of the second kind:
k 0 1 2 3 4 5 6 7 8 9 10 11 12
n
0 1
1 0 1
2 0 1 1
3 0 1 3 1
4 0 1 7 6 1
5 0 1 15 25 10 1
6 0 1 31 90 65 15 1
7 0 1 63 301 350 140 21 1
8 0 1 127 966 1701 1050 266 28 1
9 0 1 255 3025 7770 6951 2646 462 36 1
10 0 1 511 9330 34105 42525 22827 5880 750 45 1
11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1
12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1
Maximum Stirling number of the second kind with n = 100:
7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
Line 177 ⟶ 178:
 
=={{header|ALGOL W}}==
<langsyntaxhighlight lang="algolw">begin % show some Stirling numbers of the second kind %
integer MAX_STIRLING;
MAX_STIRLING := 12;
Line 195 ⟶ 196:
write( "Stirling numbers of the second kind:" );
write( " k" );
for k := 0 until MAX_STIRLING do writeon( i_w := 108, s_w := 0, k );
write( " n" );
for n := 0 until MAX_STIRLING do begin
write( i_w := 2, s_w := 0, n );
for k := 0 until n do writeon( i_w := 108, s_w := 0, s2( n, k ) );
end for_n
end
end.</lang>
</syntaxhighlight>
{{out}}
<pre>
Stirling numbers of the second kind:
k 0 1 2 3 4 5 6 7 8 9 10 11 12
n
0 1
1 0 1
2 0 1 1
3 0 1 3 1
4 0 1 7 6 1
5 0 1 15 25 10 1
6 0 1 31 90 65 15 1
7 0 1 63 301 350 140 21 1
8 0 1 127 966 1701 1050 266 28 1
9 0 1 255 3025 7770 6951 2646 462 36 1
10 0 1 511 9330 34105 42525 22827 5880 750 45 1
11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1
12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1
</pre>
 
=={{header|BASIC}}==
<langsyntaxhighlight lang="basic">10 DEFINT N,K: DEFDBL S: DEFSTR F
20 DIM S2(12,12),F(12)
30 FOR N=0 TO 12: READ F(N): NEXT N
Line 239 ⟶ 241:
140 NEXT N
150 DATA ##,##,#####,######,#######,########
160 DATA ########,#######,#######,######,#####,###,##</langsyntaxhighlight>
{{out}}
<pre> 1
Line 256 ⟶ 258:
 
=={{header|C}}==
<langsyntaxhighlight lang="c">#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
Line 317 ⟶ 319:
stirling_cache_destroy(&sc);
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 340 ⟶ 342:
=={{header|C++}}==
{{libheader|GMP}}
<langsyntaxhighlight lang="cpp">#include <algorithm>
#include <iomanip>
#include <iostream>
Line 392 ⟶ 394:
std::cout << max << '\n';
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 417 ⟶ 419:
=={{header|D}}==
{{trans|Java}}
<langsyntaxhighlight lang="d">import std.bigint;
import std.conv;
import std.functional;
Line 471 ⟶ 473:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>Stirling numbers of the second kind:
Line 491 ⟶ 493:
7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
(115 digits, k = 28)</pre>
 
=={{header|EasyLang}}==
<syntaxhighlight lang="easylang">
print "Unsigned Stirling numbers of the second kind:"
len a[] 13 ; arrbase a[] 0
len b[] 13 ; arrbase b[] 0
a[0] = 1
print 1
for n = 1 to 12
b[0] = 0
write 0 & " "
for k = 1 to n - 1
b[k] = k * a[k] + a[k - 1]
write b[k] & " "
.
b[n] = 1
write 1 & " "
print ""
swap a[] b[]
.
</syntaxhighlight>
 
=={{header|Factor}}==
{{works with|Factor|0.99 development version 2019-07-10}}
<langsyntaxhighlight lang="factor">USING: combinators.short-circuit formatting io kernel math
math.extras prettyprint sequences ;
RENAME: stirling math.extras => (stirling)
Line 514 ⟶ 537:
 
"Maximum value from the 100 _ stirling row:" print
100 <iota> [ 100 swap stirling ] map supremum .</langsyntaxhighlight>
{{out}}
<pre>
Line 538 ⟶ 561:
 
=={{header|FreeBASIC}}==
<langsyntaxhighlight lang="freebasic">dim as integer S2(0 to 12, 0 to 12) 'initially set with zeroes
dim as ubyte n, k
dim as string outstr
Line 569 ⟶ 592:
next k
print outstr
next n</langsyntaxhighlight>
<pre>Stirling numbers of the second kind
 
Line 590 ⟶ 613:
=={{header|Fōrmulæ}}==
 
{{FormulaeEntry|page=https://formulae.org/?script=examples/Stirling_numbers_of_the_second_kind}}
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation &mdash;i.e. XML, JSON&mdash; they are intended for storage and transfer purposes more than visualization and edition.
 
'''Solution'''
Programs in Fōrmulæ are created/edited online in its [https://formulae.org website], However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used.
 
'''Version 1. Recursive'''
In '''[https://formulae.org/?example=Stirling_numbers_of_the_second_kind this]''' page you can see the program(s) related to this task and their results.
 
[[File:Fōrmulæ - Stirling numbers of the second kind 01.png]]
 
'''Test case 1. Show the Stirling numbers of the second kind, S₂(n, k), up to S₂(12, 12)'''
 
[[File:Fōrmulæ - Stirling numbers of the second kind 02.png]]
 
[[File:Fōrmulæ - Stirling numbers of the second kind 03.png]]
 
'''Version 2. Non recursive'''
 
A faster, non recursive version is presented. This constructs a matrix.
 
[[File:Fōrmulæ - Stirling numbers of the second kind 04.png]]
 
'''Test case 1. Show the Stirling numbers of the second kind, S₂(n, k), up to S₂(12, 12)'''
 
[[File:Fōrmulæ - Stirling numbers of the second kind 05.png]]
 
(the result is the same as recursive version)
 
'''Test case 2. Find the maximum value of S₂(n, k) where n ≤ 100'''
 
[[File:Fōrmulæ - Stirling numbers of the second kind 06.png]]
 
[[File:Fōrmulæ - Stirling numbers of the second kind 07.png]]
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
 
import (
Line 649 ⟶ 698:
fmt.Println(max)
fmt.Printf("which has %d digits.\n", len(max.String()))
}</langsyntaxhighlight>
 
{{out}}
Line 675 ⟶ 724:
</pre>
=={{header|Haskell}}==
<langsyntaxhighlight lang="haskell">import Text.Printf (printf)
import Data.List (groupBy)
import qualified Data.MemoCombinators as Memo
Line 700 ⟶ 749:
where
table :: [[(Int, Int)]]
table = groupBy (\a b -> fst a == fst b) $ (,) <$> [0..12] <*> [0..12]</langsyntaxhighlight>
{{out}}
<pre>n/k 0 1 2 3 4 5 6 7 8 9 10 11 12
Line 759 ⟶ 808:
 
=={{header|Java}}==
<langsyntaxhighlight lang="java">
import java.math.BigInteger;
import java.util.HashMap;
Line 820 ⟶ 869:
 
}
</syntaxhighlight>
</lang>
 
{{out}}
Line 853 ⟶ 902:
is available in the second part.
 
<langsyntaxhighlight lang="jq">def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
 
# Input: {computed} (the cache)
Line 901 ⟶ 950:
| .emit,
part2(100)
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 926 ⟶ 975:
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">using Combinatorics
 
const s2cache = Dict()
Line 964 ⟶ 1,013:
println("\nThe maximum for stirling2(100, _) is: ", maximum(k-> stirlings2(BigInt(100), BigInt(k)), 1:100))
 
</langsyntaxhighlight>{{out}}
<pre>
0 1 2 3 4 5 6 7 8 9 10 11 12
Line 987 ⟶ 1,036:
=={{header|Kotlin}}==
{{trans|Java}}
<langsyntaxhighlight lang="scala">import java.math.BigInteger
 
fun main() {
Line 1,039 ⟶ 1,088:
COMPUTED[key] = result
return result
}</langsyntaxhighlight>
{{out}}
<pre>Stirling numbers of the second kind:
Line 1,059 ⟶ 1,108:
7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
(115 digits, k = 28)</pre>
 
=={{header|Lua}}==
<syntaxhighlight lang="lua">
do -- show some Stirling numbers of the second kind
local MAX_STIRLING = 12;
-- construct a matrix of Stirling numbers up to max n, max n
local s2 = {}
for n = 0, MAX_STIRLING do
s2[ n ] = {}
for k = 0, MAX_STIRLING do s2[ n ][ k ] = 0 end
end
for n = 0, MAX_STIRLING do s2[ n ][ n ] = 1 end
for n = 0, MAX_STIRLING - 1 do
for k = 1, n do
s2[ n + 1 ][ k ] = k * s2[ n ][ k ] + s2[ n ][ k - 1 ]
end
end
io.write( "Stirling numbers of the second kind:\n" )
io.write( " k" )
for k = 0, MAX_STIRLING do io.write( string.format( "%8d", k ) ) end
io.write( "\n" )
io.write( " n\n" );
for n = 0, MAX_STIRLING do
io.write( string.format( "%2d", n ) )
for k = 0, n do io.write( string.format( "%8d", s2[ n ][ k ] ) ) end
io.write( "\n" )
end
end
</syntaxhighlight>
{{out}}
<pre>
Stirling numbers of the second kind:
k 0 1 2 3 4 5 6 7 8 9 10 11 12
n
0 1
1 0 1
2 0 1 1
3 0 1 3 1
4 0 1 7 6 1
5 0 1 15 25 10 1
6 0 1 31 90 65 15 1
7 0 1 63 301 350 140 21 1
8 0 1 127 966 1701 1050 266 28 1
9 0 1 255 3025 7770 6951 2646 462 36 1
10 0 1 511 9330 34105 42525 22827 5880 750 45 1
11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1
12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1
</pre>
 
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">TableForm[Array[StirlingS2, {n = 12, k = 12} + 1, {0, 0}], TableHeadings -> {"n=" <> ToString[#] & /@ Range[0, n], "k=" <> ToString[#] & /@ Range[0, k]}]
Max[Abs[StirlingS2[100, #]] & /@ Range[0, 100]]</langsyntaxhighlight>
{{out}}
<pre> k=0 k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8 k=9 k=10 k=11 k=12
Line 1,082 ⟶ 1,179:
=={{header|Nim}}==
As for Stirling numbers of first kind, a simple program using recursive definition is enough to solve the task when not using big numbers.
<langsyntaxhighlight Nimlang="nim">import sequtils, strutils
 
proc s2(n, k: Natural): Natural =
Line 1,095 ⟶ 1,192:
for k in 0..n:
stdout.write ($s2(n, k)).align(8)
stdout.write '\n'</langsyntaxhighlight>
 
{{out}}
Line 1,116 ⟶ 1,213:
Now, to solve the second part of the task, we have to use big numbers. As for Stirling numbers of first kind, we also use a cache to avoid to repeat multiple times the same computations.
{{libheader|bignum}}
<langsyntaxhighlight Nimlang="nim">import tables
import bignum
 
Line 1,135 ⟶ 1,232:
 
echo "Maximum Stirling number of the second kind with n = 100:"
echo max</langsyntaxhighlight>
 
{{out}}
Line 1,142 ⟶ 1,239:
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">use strict;
use warnings;
use bigint;
Line 1,173 ⟶ 1,270:
 
say "\nMaximum value from the S2(100, *) row:";
say max map { Stirling2(101,$_) } 0..100;</langsyntaxhighlight>
{{out}}
<pre>Unsigned Stirling2 numbers of the second kind: S2(n, k):
Line 1,197 ⟶ 1,294:
{{libheader|Phix/mpfr}}
{{trans|Go}}
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<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 1,236 ⟶ 1,333:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</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;">"\nThe maximum S2(100,k): %s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m100</span><span style="color: #0000FF;">)))</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,261 ⟶ 1,358:
=={{header|Prolog}}==
{{works with|SWI Prolog}}
<langsyntaxhighlight lang="prolog">:- dynamic stirling2_cache/3.
 
stirling2(N, N, 1):-!.
Line 1,302 ⟶ 1,399:
writeln('Maximum value of S2(n,k) where n = 100:'),
max_stirling2(100, M),
writeln(M).</langsyntaxhighlight>
 
{{out}}
Line 1,325 ⟶ 1,422:
=={{header|Python}}==
{{trans|Java}}
<syntaxhighlight lang="python">
<lang Python>
computed = {}
 
Line 1,365 ⟶ 1,462:
print("{0}\n({1} digits, k = {2})\n".format(previous, len(str(previous)), k - 1))
break
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,390 ⟶ 1,487:
=={{header|Quackery}}==
 
<langsyntaxhighlight Quackerylang="quackery"> [ dip number$
over size -
space swap of
Line 1,421 ⟶ 1,518:
0 100 times
[ 100 i^ 1+ s2 max ]
echo cr</langsyntaxhighlight>
 
{{out}}
Line 1,446 ⟶ 1,543:
{{works with|Rakudo|2019.07.1}}
 
<syntaxhighlight lang="raku" perl6line>sub Stirling2 (Int \n, Int \k) {
((1,), { (0, |@^last) »+« (|(@^last »*« @^last.keys), 0) } … *)[n;k]
}
Line 1,463 ⟶ 1,560:
 
say "\nMaximum value from the S2(100, *) row:";
say (^100).map( { Stirling2 100, $_ } ).max;</langsyntaxhighlight>
{{out}}
<pre>Stirling numbers of the second kind: S2(n, k):
Line 1,486 ⟶ 1,583:
=={{header|REXX}}==
Some extra code was added to minimize the displaying of the column widths.
<syntaxhighlight lang="text">/*REXX program to compute and display Stirling numbers of the second kind. */
parse arg lim . /*obtain optional argument from the CL.*/
if lim=='' | lim=="," then lim= 12 /*Not specified? Then use the default.*/
Line 1,523 ⟶ 1,620:
end /*c*/
say center(r, wgi) strip( substr($,2), 'T') /*display a single row of the grid. */
end /*r*/ /*stick a fork in it, we're all done. */</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default input:}}
<pre>
Line 1,545 ⟶ 1,642:
The maximum value (which has 115 decimal digits):
7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
</pre>
 
=={{header|RPL}}==
{{works with|RPL|HP49-C}}
« '''IF''' DUP2 AND NOT '''THEN''' ==
'''ELSE'''
SWAP 1 - OVER
DUP2 1 - <span style="color:blue">S2</span> 4 ROLLD <span style="color:blue">S2</span> * +
'''END'''
» '<span style="color:blue">S2</span>' STO <span style="color:grey">''@ ( n k → S2(n,k) )''</span>
 
12 12 « <span style="color:blue">S2</span> » LCXM
{{out}}
<pre>
1: [[ 1 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1 1 0 0 0 0 0 0 0 0 0 0 ]
[ 1 3 1 0 0 0 0 0 0 0 0 0 ]
[ 1 7 6 1 0 0 0 0 0 0 0 0 ]
[ 1 15 25 10 1 0 0 0 0 0 0 0 ]
[ 1 31 90 65 15 1 0 0 0 0 0 0 ]
[ 1 63 301 350 140 21 1 0 0 0 0 0 ]
[ 1 127 966 1701 1050 266 28 1 0 0 0 0 ]
[ 1 255 3025 7770 6951 2646 462 36 1 0 0 0 ]
[ 1 511 9330 34105 42525 22827 5880 750 45 1 0 0 ]
[ 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 0 ]
[ 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 ]]
</pre>
 
=={{header|Ruby}}==
 
<langsyntaxhighlight lang="ruby">@memo = {}
 
def sterling2(n, k)
Line 1,573 ⟶ 1,696:
puts "\nMaximum value from the sterling2(100, k)";
puts (1..100).map{|a| sterling2(100,a)}.max
</syntaxhighlight>
</lang>
{{out}}<pre>Sterling2 numbers:
n/k 0 1 2 3 4 5 6 7 8 9 10 11 12
Line 1,594 ⟶ 1,717:
 
</pre>
 
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">func S2(n, k) { # Stirling numbers of the second kind
stirling2(n, k)
}
Line 1,615 ⟶ 1,739:
say "\nMaximum value from the S2(#{n}, *) row:"
say { S2(n, _) }.map(^n).max
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,638 ⟶ 1,762:
 
Alternatively, the '''S2(n,k)''' function can be defined as:
<langsyntaxhighlight lang="ruby">func S2((0), (0)) { 1 }
func S2(_, (0)) { 0 }
func S2((0), _) { 0 }
func S2(n, k) is cached { S2(n-1, k)*k + S2(n-1, k-1) }</langsyntaxhighlight>
 
=={{header|Tcl}}==
 
{{trans|Java}}
<langsyntaxhighlight Tcllang="tcl">proc S2 {n k} {
set nk [list $n $k]
if {[info exists ::S2cache($nk)]} {
Line 1,695 ⟶ 1,819:
}
}
main</langsyntaxhighlight>
{{out}}
<pre>
Line 1,720 ⟶ 1,844:
=={{header|Visual Basic .NET}}==
{{trans|Java}}
<langsyntaxhighlight lang="vbnet">Imports System.Numerics
 
Module Module1
Line 1,789 ⟶ 1,913:
End Sub
 
End Module</langsyntaxhighlight>
{{out}}
<pre>Stirling numbers of the second kind:
Line 1,814 ⟶ 1,938:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight ecmascriptlang="wren">import "./big" for BigInt
import "./fmt" for Fmt
 
var computed = {}
Line 1,852 ⟶ 1,976:
break
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,877 ⟶ 2,001:
 
=={{header|zkl}}==
<langsyntaxhighlight lang="zkl">fcn stirling2(n,k){
var seen=Dictionary(); // cache for recursion
if(n==k) return(1); // (0.0)==1
Line 1,885 ⟶ 2,009:
if(Void==(s2 := seen.find(z2))){ s2 = seen[z2] = stirling2(n-1,k-1) }
k*s1 + s2; // k is first to cast to BigInt (if using BigInts)
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">// calculate entire table (cached), find max, find num digits in max
N,mx := 12, [1..N].apply(fcn(n){ [1..n].apply(stirling2.fp(n)) }).flatten() : (0).max(_);
fmt:="%%%dd".fmt("%d".fmt(mx.numDigits + 1)).fmt; // "%9d".fmt
Line 1,893 ⟶ 2,017:
foreach row in ([0..N]){
println("%3d".fmt(row), [0..row].pump(String, stirling2.fp(row), fmt));
}</langsyntaxhighlight>
{{out}}
<pre style="font-size:83%">
Line 1,913 ⟶ 2,037:
</pre>
{{libheader|GMP}} GNU Multiple Precision Arithmetic Library
<langsyntaxhighlight lang="zkl">var [const] BI=Import("zklBigNum"); // libGMP
N=100;
S2100:=[BI(2)..N].apply(stirling2.fp(BI(N))).reduce(fcn(m,n){ m.max(n) });
println("Maximum value from the S2(%d,*) row (%d digits):".fmt(N,S2100.numDigits));
println(S2100);</langsyntaxhighlight>
{{out}}
<pre style="font-size:83%">
Aerobar
1,150

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/292631...362915"