Perl Weekly Challenge 108: Bell Numbers

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\).

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.

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.

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\).

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.

Can't be much simpler than this.

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

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 oeis (110 => 10)

A straight forward implementation of the algorithm explained above:

my @bell = [1];
for (my $x = 1; $x < $COUNT - 1; $x ++) {
$bell [$x] [0] = $bell [$x - 1] [-1];
for (my $y = 1; $y <= $x; $y ++) {
    $bell [$x] [$y] = $bell [$x] [$y - 1] + $bell [$x - 1] [$y - 1]
}

$, = ", ";
say 1, map {$$_ [-1]} @bell;

Find the full program on GitHub.

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 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 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.

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.

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

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.

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 ("")

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.