Perl Weekly Challenge 108: Bell Numbers

by Abigail

Challenge

Example

• $$B_0$$: 1 as you can only have one partition of zero element set.
• $$B_1$$: 1 as you can only have one partition of one element set $$\{a\}$$.
• $$B_2$$: 2
• $$\{a\}\{b\}$$
• $$\{a,b\}$$
• $$B_3$$: 5
• $$\{a\}\{b\}\{c\}$$
• $$\{a,b\}\{c\}$$
• $$\{a\}\{b,c\}$$
• $$\{a,c\}\{b\}$$
• $$\{a,b,c\}$$
• $$B_4$$: 15
• $$\{a\}\{b\}\{c\}\{d\}$$
• $$\{a,b,c,d\}$$
• $$\{a,b\}\{c,d\}$$
• $$\{a,c\}\{b,d\}$$
• $$\{a,d\}\{b,c\}$$
• $$\{a,b\}\{c\}\{d\}$$
• $$\{a,c\}\{b\}\{d\}$$
• $$\{a,d\}\{b\}\{c\}$$
• $$\{b,c\}\{a\}\{d\}$$
• $$\{b,d\}\{a\}\{c\}$$
• $$\{c,d\}\{a\}\{b\}$$
• $$\{a\}\{b,c,d\}$$
• $$\{b\}\{a,c,d\}$$
• $$\{c\}\{a,b,d\}$$
• $$\{d\}\{a,b,c\}$$

Discussion

The Bell Numbers have their own entry in the OEIS. We can look up the first ten Bell Numbers: $$1$$, $$1$$, $$2$$, $$5$$, $$15$$, $$52$$, $$203$$, $$877$$, $$4140$$, and $$21147$$.

Hello, World!

The simplest way would be just to take those ten numbers, and print them. This means we have yet again a challenge which is just a glorified Hello, World program.

Fetch

If we don't want to do exactly what the challenge asks from us (print the first ten Bell Numbers), we could instead fetch the numbers from the OEIS and print them. For instance, by using the OEIS module which we recently uploaded to CPAN.

There is limited usefulness in this though — it's not that the Bell Numbers will change in the future.

Calculate

Alternatively, we could calculate the first ten Bell Numbers. There are many ways to calculate the numbers, but we opt to create a Bell Triangle.

The first rows of the Bell Triangle are as follows:

 1
1  2
2  3  5
5  7 10 15
15 20 27 37 52


And we have the following rules to construct the triangle:

• The top row contains a single $$1$$.
• For each other row:
• The row will have one more element than the previous row.
• The first (left most) element is equal to the last (right most) element of the previous row.
• Each other element is the sum of the element to its left on the same row, and the element on the previous row right above that.

Or, formalized:

Let $$b_{r, c}$$ be the element on row $$r$$ and column $$c$$. (This implies $$0 \leq c \leq r$$, with the top most element being $$b_{0, 0}$$.) Then

$b_{r, c} = \begin{cases} 1, & \text{if } r = c = 0 \\ b_{r - 1, r - 1}, & \text{if } r > 0, c = 0 \\ b_{r, c - 1} + b_{r - 1, c - 1}, & \text{if } r \geq c > 0 \end{cases}$

If we then generate the first nine rows of the Bell Triangle, and take the last elements of each row, we get the second to tenth Bell Numbers. The first Bell Number is $$1$$.

Solutions

Depending on the language, we solve the challenge in one or more of the strategies explained above. All languages will implement the Hello, World! strategy. For some languages, we also calculate the Bell Triangle. And in Perl, we also implement a fetch strategy.

Languages which solve the problem in more than one way take a command line argument indicating the strategy to follow. This argument should be one of plain (the default), fetch (which fetches the numbers from the OEIS, or compute, which computes the first rows of the Bell Triangle.

We will only show the the plain solution for Perl; for the other implementations, see the GitHub links below.

Perl

plain

Can't be much simpler than this.

say "1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147"


fetch

We're using the new module OEIS which export a single method, oeis, which takes two arguments: the sequence to fetch, and the number of elements to return.

use OEIS;
}

$, = ", "; say 1, map {$$_ [-1]} @bell;  Find the full program on GitHub. AWK The algorithm above is simply written down in AWK: BEGIN { COUNT = 10 bell [1, 1] = 1 for (x = 2; x < COUNT; x ++) { bell [x, 1] = bell [x - 1, x - 1] for (y = 2; y <= x; y ++) { bell [x, y] = bell [x, y - 1] + bell [x - 1, y - 1] } } printf "1" for (x = 1; x < COUNT; x ++) { printf ", %d", bell [x, x] } printf "\n" }  Find the full program on GitHub. Bash Bash doesn't have two dimensional arrays. So, we're using a function index which takes two arguments (an x and a y coordinate) and returns a single index. The return value is written in the global variable idx. We then get: set -f COUNT=10 function index () { local x=$1
local y=$2 idx=$((COUNT * x + y))
}

bell[0]=1
for ((x = 1; x < COUNT - 1; x ++))
do   index $x 0; i1=$idx
index $((x - 1))$((x - 1)); i2=$idx bell[$i1]=${bell[$i2]}
for ((y = 1; y <= x; y ++))
do  index   $x$y;       i1=$idx index$x       $((y - 1)); i2=$idx
index $((x - 1))$((y - 1)); i3=$idx bell[$i1]=$((bell[i2] + bell[i3])) done done printf "1" for ((x = 0; x < COUNT - 1; x ++)) do index$x $x; printf ", %d"${bell[\$idx]}
done
echo


Find the full program on GitHub.

C

C requires us to manage our own memory. Other than that, it's the same algorithm:

# define COUNT   10

typedef int number;  /* Change if we want large numbers */
char * fmt = "%d";   /* Should match typedef            */

int main (int argc, char * argv []) {
number ** bell;
if ((bell = (number **) malloc ((COUNT - 1) * sizeof (number *)))
== NULL) {
perror ("Mallocing bell failed");
exit (1);
}
if ((bell [0] = (number *) malloc (sizeof (number))) == NULL) {
perror ("Mallocing row failed");
exit (1);
}
bell [0] [0] = 1;
for (int x = 1; x < COUNT - 1; x ++) {
if ((bell [x] = (number *) malloc ((x + 1) * sizeof (number)))
== NULL) {
perror ("Mallocing row failed");
exit (1);
}
bell [x] [0] = bell [x - 1] [x - 1];
for (int y = 1; y <= x; y ++) {
bell [x] [y] = bell [x] [y - 1] + bell [x - 1] [y - 1];
}
}

/*
* Print the right diagonal
*/
printf (fmt, 1);
for (int x = 0; x < COUNT - 1; x ++) {
printf (", ");
printf (fmt, bell [x] [x]);
}
printf ("\n");
exit (0);
}


Find the full program on GitHub.

Lua

Same algorithm:

local COUNT = 10
local bell  = {}

bell [0] = {}
bell [0] [0] = 1
for x = 1, COUNT - 2
do  bell [x] = {}
bell [x] [0] = bell [x - 1] [x - 1]
for  y = 1, x
do   bell [x] [y] = bell [x] [y - 1] + bell [x - 1] [y - 1]
end
end

io . write (1)
for x = 0, COUNT - 2
do  io . write (", " .. bell [x] [x])
end
io . write ("\n")


Find the full program on GitHub.

Node.js

let COUNT = 10
let bell  = [[ 1 ]]
let x
for (x = 1; x < COUNT - 1; x ++) {
bell [x] = [bell [x - 1] [x - 1]]
let y
for (y = 1; y <= x; y ++) {
bell [x] [y] = bell [x] [y - 1] + bell [x - 1] [y - 1]
}
}

process . stdout . write ("1")
for (x = 0; x < COUNT - 1; x ++) {
process . stdout . write (", " + bell [x] [x] . toString ())
}
process . stdout . write ("\n")


Find the full program on GitHub.

Python

Python doesn't autovivify array elements when indexing out of bounds. So we use the append method to add elements to arrays.

COUNT = 10
bell  = [[1]]
for x in range (1, COUNT - 1):
bell . append ([bell [x - 1] [x - 1]])
for y in range (1, x + 1):
bell [x] . append (bell [x] [y - 1] + bell [x - 1] [y - 1])

print (1, end = '')
for x in range (0, COUNT - 1):
print (",", bell [x] [x], end = '')

print ("")


Find the full program on GitHub.

Ruby

COUNT = 10
bell  = [[1]]
for  x in 1 .. COUNT - 2
bell [x] = [bell [x - 1] [x - 1]]
for  y in 1 .. x
bell [x] [y] = bell [x] [y - 1] + bell [x - 1] [y - 1]
end
end
print (1)
for  x in 0 .. COUNT - 2
print (", ")
print (bell [x] [x])
end
puts ("")


Find the full program on GitHub.

Other languages

We also have simple solutions for BASIC, bc, Befunge-93, Cobol, Csh, Erlang, Forth, Fortran, Go, Java, m4, OCaml, Pascal, PHP, PostScript, R, Rexx, Scheme, sed, SQL, and Tcl.