Stirling numbers of the second kind: Difference between revisions

From Rosetta Code
Content added Content deleted
(Added Go)
(→‎{{header|REXX}}: used a minimum width for any column to save screen acreage. .)
Line 244: Line 244:
@.0.j = 0; @.j.0 = 0 /* " " zero values. */
@.0.j = 0; @.j.0 = 0 /* " " zero values. */
end /*j*/
end /*j*/
max#= 0 /* [↓] calculate values for the grid. */
max#.= 0 /* [↓] calculate values for the grid. */
do n=0 for lim+1; np= n + 1
do n=0 for lim+1; np= n + 1
do k=1 for lim; km= k - 1
do k=1 for lim; km= k - 1
@.np.k = k * @.n.k + @.n.km /*calculate a number in the grid. */
@.np.k = k * @.n.k + @.n.km /*calculate a number in the grid. */
max#= max(max#, @.n.k) /*find " " value " " " */
max#.k= max(max#.k, @.n.k) /*find the maximum value for a column. */
⚫
max#.b= max(max#.b, @.n.k) /*find the maximum value for all rows. */
end /*k*/
end /*k*/
end /*n*/
end /*n*/
/* [↓] only show the maximum value ? */
/* [↓] only show the maximum value ? */
w= length(max#) /*calculate max width of all numbers. */
do k=0 for lim+1 /*find max column width for each column*/
max#.a= max#.a + length(max#.k)
⚫
if olim<0 then do; say 'The maximum value (which has ' w " decimal digits):"
end /*k*/
⚫
say max# /*display maximum number in the grid. */

w= length(max#.b) /*calculate max width of all numbers. */
⚫
if olim<0 then do; say 'The maximum value (which has ' w " decimal digits):"
say max#.b /*display maximum number in the grid. */
exit /*stick a fork in it, we're all done. */
exit /*stick a fork in it, we're all done. */
end
end
wi= max(3, length(lim+1) ) /*the maximum width of the grid's index*/
wi= max(3, length(lim+1) ) /*the maximum width of the grid's index*/
say 'row' center('columns', (w+1)*(lim+1), '═') /*display the header of the grid. */
say 'row' center('columns', max#.a + lim, '═') /*display the header of the grid. */


do r=0 for lim+1; $= /* [↓] display the grid to the term. */
do r=0 for lim+1; $= /* [↓] display the grid to the term. */
do c=0 for lim+1 until c>=r /*build a row of grid, 1 col at a time.*/
do c=0 for lim+1 until c>=r /*build a row of grid, 1 col at a time.*/
$= $ right(@.r.c, w) /*append a column to a row of the grid.*/
$= $ right(@.r.c, length(max#.c) ) /*append a column to a row of the grid.*/
end /*c*/
end /*c*/
say right(r,wi) strip(substr($,2), 'T') /*display a single row of the grid. */
say right(r,wi) strip(substr($,2), 'T') /*display a single row of the grid. */
Line 268: Line 273:
{{out|output|text=&nbsp; when using the default input:}}
{{out|output|text=&nbsp; when using the default input:}}
<pre>
<pre>
row ══════════════════════════════columns══════════════════════════════
row ════════════════════════════════════════════════columns═════════════════════════════════════════════════
0 1
0 1
1 0 1
1 0 1
2 0 1 1
2 0 1 1
3 0 1 3 1
3 0 1 3 1
4 0 1 7 6 1
4 0 1 7 6 1
5 0 1 15 25 10 1
5 0 1 15 25 10 1
6 0 1 31 90 65 15 1
6 0 1 31 90 65 15 1
7 0 1 63 301 350 140 21 1
7 0 1 63 301 350 140 21 1
8 0 1 127 966 1701 1050 266 28 1
8 0 1 127 966 1701 1050 266 28 1
9 0 1 255 3025 7770 6951 2646 462 36 1
9 0 1 255 3025 7770 6951 2646 462 36 1
10 0 1 511 9330 34105 42525 22827 5880 750 45 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
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
12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1
</pre>
</pre>
{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> -100 </tt>}}
{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> -100 </tt>}}

Revision as of 10:45, 16 August 2019

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: 

   S2(n, 0) and S2(0, k) = 0 # for n, k > 0
   S2(n, n) = 1
   S2(n + 1, k) = k * S2(n, k) + S2(n, k - 1)


Task
  • Write a routine (function, procedure, whatever) to find Stirling numbers of the second kind. There are several methods to generate Stirling numbers of the second kind. You are free to choose the most appropriate for your language. If your language has a built-in, or easily, publicly available library implementation, it is acceptable to use that.
  • Using the routine, generate and show here, on this page, a table (or triangle) showing the Stirling numbers of the second kind, S2(n, k), up to S2(12, 12). it is optional to show the row / column for n == 0 and k == 0. It is optional to show places where S2(n, k) == 0 (when k > n).
  • If your language supports large integers, find and show here, on this page, the maximum value of S2(n, k) where n == 100.


See also


Related Tasks



Factor

Works with: Factor version 0.99 development version 2019-07-10

<lang factor>USING: combinators.short-circuit formatting io kernel math math.extras prettyprint sequences ; RENAME: stirling math.extras => (stirling) IN: rosetta-code.stirling-second

! Tweak Factor's in-built stirling function for k=0

stirling ( n k -- m )
   2dup { [ = not ] [ nip zero? ] } 2&&
   [ 2drop 0 ] [ (stirling) ] if ;

"Stirling numbers of the second kind: n k stirling:" print "n\\k" write 13 dup [ "%8d" printf ] each-integer nl

<iota> [ 

   dup dup "%-2d " printf [0,b] [
       stirling "%8d" printf
   ] with each nl

] each nl

"Maximum value from the 100 _ stirling row:" print 100 <iota> [ 100 swap stirling ] map supremum .</lang>

Output:
Stirling numbers of the second kind: n k stirling:
n\k       0       1       2       3       4       5       6       7       8       9      10      11      12
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 value from the 100 _ stirling row:
7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674

Go

<lang go>package main

import ( 

   "fmt"
   "math/big"

)

func main() { 

   limit := 100
   last := 12
   s2 := make([][]*big.Int, limit+1)
   for n := 0; n <= limit; n++ {
       s2[n] = make([]*big.Int, limit+1)
       for k := 0; k <= limit; k++ {
           s2[n][k] = new(big.Int)
       }
       s2[n][n].SetInt64(int64(1))
   }
   var t big.Int
   for n := 1; n <= limit; n++ {
       for k := 1; k <= n; k++ {
           t.SetInt64(int64(k))
           t.Mul(&t, s2[n-1][k])
           s2[n][k].Add(&t, s2[n-1][k-1])
       }
   }
   fmt.Println("Stirling numbers of the second kind: S2(n, k):")
   fmt.Printf("n/k")
   for i := 0; i <= last; i++ {
       fmt.Printf("%9d ", i)
   }
   fmt.Printf("\n--")
   for i := 0; i <= last; i++ {
       fmt.Printf("----------")
   }
   fmt.Println()
   for n := 0; n <= last; n++ {
       fmt.Printf("%2d ", n)
       for k := 0; k <= n; k++ {
           fmt.Printf("%9d ", s2[n][k])
       }
       fmt.Println()
   }
   fmt.Println("\nMaximum value from the S2(100, *) row:")
   max := new(big.Int).Set(s2[limit][0])
   for k := 1; k <= limit; k++ {
       if s2[limit][k].Cmp(max) > 0 {
           max.Set(s2[limit][k])
       }
   }
   fmt.Println(max)
   fmt.Printf("which has %d digits.\n", len(max.String()))

}</lang>

Output:
Stirling numbers of the second kind: S2(n, k):
n/k        0         1         2         3         4         5         6         7         8         9        10        11        12 
------------------------------------------------------------------------------------------------------------------------------------
 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 value from the S2(100, *) row:
7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
which has 115 digits.

Julia

<lang julia>using Combinatorics

function printstirling2table(kmax) 

   println("  ", mapreduce(i -> lpad(i, 10), *, 0:kmax))

   sstring(n, k) = begin i = stirlings2(n, k); lpad(k > n && i == 0 ? "" : i, 10) end

   for n in 0:kmax
       println(rpad(n,2) * mapreduce(k -> sstring(n, k), *, 0:kmax))
   end

end

printstirling2table(12)

</lang>

Output:
           0         1         2         3         4         5         6         7         8         9        10        11        12
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

Perl 6

Works with: Rakudo version 2019.07.1

<lang perl6>sub Stirling2 (Int \n, Int \k) { 

   ((1,), { (0, |@^last) »+« (|(@^last »*« @^last.keys), 0) } … *)[n;k]

}

my $upto = 12;

my $mx = (1..^$upto).map( { Stirling2($upto, $_) } ).max.chars;

put 'Stirling numbers of the second kind: S2(n, k):'; put 'n\k', (0..$upto)».fmt: "%{$mx}d";

for 0..$upto -> $row { 

   $row.fmt('%-3d').print;
   put (0..$row).map( { Stirling2($row, $_) } )».fmt: "%{$mx}d";

}

say "\nMaximum value from the S2(100, *) row:"; say (^100).map( { Stirling2 100, $_ } ).max;</lang>

Output:
Stirling numbers of the second kind: S2(n, k):
n\k      0       1       2       3       4       5       6       7       8       9      10      11      12
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 value from the S2(100, *) row:
7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674

REXX

<lang>/*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.*/ olim= lim /*save the original value of LIM. */ lim= abs(lim) /*only use the absolute value of LIM. */ numeric digits max(9, 2*lim) /*(over) specify maximum number in grid*/ @.= 

       do j=0  for lim+1
       @.j.j = 1;  if j==0  then iterate        /*define the right descending diagonal.*/
       @.0.j = 0;  @.j.0 = 0                    /*   "    "  zero  values.             */
       end   /*j*/

max#.= 0 /* [↓] calculate values for the grid. */ 

       do   n=0  for lim+1;         np= n + 1
         do k=1  for lim;           km= k - 1
         @.np.k = k * @.n.k  +  @.n.km          /*calculate a number in the grid.      */
         max#.k= max(max#.k, @.n.k)             /*find the maximum value for a column. */
         max#.b= max(max#.b, @.n.k)             /*find the maximum value for all rows. */
         end   /*k*/
       end     /*n*/
                                                /* [↓]  only show the maximum value ?  */
       do k=0  for lim+1                        /*find max column width for each column*/
       max#.a= max#.a + length(max#.k)
       end   /*k*/

w= length(max#.b) /*calculate max width of all numbers. */ if olim<0 then do; say 'The maximum value (which has ' w " decimal digits):" 

                    say max#.b                  /*display maximum number in the grid.  */
                    exit                        /*stick a fork in it,  we're all done. */
               end

wi= max(3, length(lim+1) ) /*the maximum width of the grid's index*/ say 'row' center('columns', max#.a + lim, '═') /*display the header of the grid. */ 

       do   r=0  for lim+1; $=                  /* [↓]  display the grid to the term.  */
         do c=0  for lim+1  until c>=r          /*build a row of grid, 1 col at a time.*/
         $= $  right(@.r.c, length(max#.c) )    /*append a column to a row of the grid.*/
         end   /*c*/
       say right(r,wi)  strip(substr($,2), 'T') /*display a single row of the grid.    */
       end     /*r*/                            /*stick a fork in it,  we're all done. */</lang>
output   when using the default input:
row ══════════════════════════════columns══════════════════════════════
  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
output   when using the input of:     -100 
The maximum value  (which has  115  decimal digits):
7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
Retrieved from "https://rosettacode.org/wiki/Stirling_numbers_of_the_second_kind?oldid=292577"