Calculating Bell numbers in a single tweet

May 23, 2012 at 12:48 pm | Posted in Clojure, Programming | 6 Comments

Recently I stumbled upon a white paper by Roger Sessions called “The Mathematics of IT Simplification”. In this paper he describes an approach called synergistic partitioning, which is based on the mathematics of sets, equivalence relations, and partitions. One of the topics that comes up in this article is how many ways there are to partition N elements. The answer to this is well-known and called the Nth Bell number.

The 52 partitions of a set with 5 elements

The Wikipedia page that explains the Bell number also shows two implementations on how to calculate them, one in Ruby and the other one in Python. The Ruby version needs 17 lines of code, the Python version 12 lines. I have the peculiar habit of intriguing/annoying my colleagues at work with the statement that using Clojure the solution to any programming problem fits into one single tweet. In other words: 140 characters.

I’ll start with my first attempt:

(defn append-ele [s x] (concat s (list (+ x (last s)))))

(defn next-row [s]
  (reduce append-ele (list (last s)) s))

(defn bell [n]
  (loop [n n s '(1) b s]
    (if (= n 1)
      (reverse b)
      (recur (dec n) (next-row s) (cons (last s) b)))))

(println (bell 9))

The first function (append-ele) appends a single new element to a row in the Bell triangle (explained in the Wikipedia article). In several ways this implementation is suboptimal since concat can only concatenate sequences, so I have to convert the single element to a list first. And what’s worse, appending at the end of a sequence is expensive since it’s computation is O(N), while prepending would only take one single operation.

The function next-row calculates the next row in the Bell triangle. This row always starts with the last element of the previous row. I implemented this by a simple reduce over the elements of the previous row.

And finally the function bell returns a sequence with the first n Bell numbers. I use a loop/recur to avoid a stack overflow. The sequence of Bell numbers is constructed in reverse order, so at the end (line 9) I have to call reverse.

While this version is already pretty short (10 lines, without the printing), this still won’t fit in a single tweet. So the next step was to remove the first two helper functions and inline all the code into a single function. Warning: this is not good coding practice! With this disclaimer, here is the resulting code:

(defn bell [n]
  (loop [n n s '(1) b s]
    (if (= n 1)
      (reverse b)
      (recur (dec n)
             (reduce #(concat % (list (+ %2 (last %)))) (list (last s)) s)
             (cons (last s) b)))))

Without the whitespace this implementation is 170 characters. Almost there! As you can see there are still some ‘expensive’ keywords like concat and reverse (6 and 7 characters!) and some annoying conversions from single numbers to lists. The only way to avoid this is to use a specialized data structure like vector instead of a sequence:

(defn bell [n]
  (loop [n n s [1] b s]
    (if (= n 1)
      b
      (recur (dec n)
             (reduce #(conj % (+ %2 (last %))) [(last s)] s)
             (conj b (last s))))))

Finally the code (without the indentation) fits into 140 characters. One caveat: I use conj which nicely appends an element to the end of a vector. However this behaviour of conj is not guaranteed. It is allowed to add an element anywhere in a sequence. When you use a list for example, the element is prepended. Because of this he above algorithm is O(N^2).

I will leave it as an exercise for the reader to implement the Bell number calculation as a lazy sequence so that you can use for example (take 9 (bell)). Have fun.