Write a script to display top 10 Bell Numbers. Please refer to wikipedia page for more informations.

- \(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\}\)

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

Find the full program on GitHub.

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

Find the full program on GitHub.

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.