How to resolve the algorithm Stirling numbers of the second kind step by step in the zkl programming language

Published on 12 May 2024 09:40 PM
#Zkl

How to resolve the algorithm Stirling numbers of the second kind step by step in the zkl programming language

Table of Contents

Problem Statement

Stirling numbers of the second kind, or Stirling partition numbers, are the number of ways to partition a set of n objects into k non-empty subsets. They are closely related to Bell numbers, and may be derived from them.

Stirling numbers of the second kind obey the recurrence relation:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Stirling numbers of the second kind step by step in the zkl programming language

Source code in the zkl programming language

fcn stirling2(n,k){
   var seen=Dictionary();	// cache for recursion
   if(n==k)       return(1);	// (0.0)==1
   if(n<1 or k<1) return(0);
   z1,z2 := "%d,%d".fmt(n-1,k), "%d,%d".fmt(n-1,k-1);
   if(Void==(s1 := seen.find(z1))){ s1 = seen[z1] = stirling2(n-1,k)   }
   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)
}

// 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
println("Stirling numbers of the second kind: S2(n,k):");
println("n\\k",[0..N].pump(String,fmt));
foreach row in ([0..N]){
   println("%3d".fmt(row), [0..row].pump(String, stirling2.fp(row), fmt));
}

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

You may also check:How to resolve the algorithm Averages/Median step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Dynamic variable names step by step in the PowerShell programming language
You may also check:How to resolve the algorithm Return multiple values step by step in the 6502 Assembly programming language
You may also check:How to resolve the algorithm Strip a set of characters from a string step by step in the NewLISP programming language
You may also check:How to resolve the algorithm Non-decimal radices/Convert step by step in the Maple programming language