## Calculating Bell numbers in a single tweet

May 23, 2012 at 12:48 pm | Posted in Clojure, Programming | 6 CommentsRecently 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 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.

## 6 Comments »

RSS feed for comments on this post. TrackBack URI

### Leave a Reply

Create a free website or blog at WordPress.com.

Entries and comments feeds.

Reblogged this on martin remy and commented:

Less isn’t always more when it comes to code and readability, but shrinking code is a fun sport and in this case, less is definitely cooler. Nicely done. Clojure FTW.

Comment by Martin Remy— May 23, 2012 #

(def bell

(cons 1

(map last

(iterate

(fn [xs]

(reduce #(conj % (+ %2 (last %)))

[(last xs)] xs))

[1]))))

Comment by Javier Neira (@jneira)— May 24, 2012 #

Nothing special about Clojure. Wikipedia code is not optimized for size. You can get a tweet-sized version in Python as well. The one below is 129 chars with indentation.

def B(N):

A=[1]+[0]*N

for n in range(N-1):

x,A[0]=A[0],A[n]

for i in range(N): x,A[i+1]=A[i+1],A[i]+x

return A[-2]

Comment by misof— June 7, 2012 #

Nice!

Now lets wait for the first Java version that fits into one tweet 😉

Comment by maurits— June 7, 2012 #

Don’t use `last` on a vector. Use `peek` instead — it’s much faster.

Comment by SI Hayakawa— June 21, 2013 #