Enumerating set partitions with Bell numbers and Stirling numbers of the second kind


Just for fun, today's Little Program is going to generate set partitions. (Why? Because back in 2005, somebody asked about it on an informal mailing list, suggesting it would be an interesting puzzle, and now I finally got around to solving it.)

The person who asked the question said,

Below we show the partitions of [4]. The periods separate the individual sets so that, for example, 1.23.4 is the partition {{1},{2,3},{4}}.

1 blocks:

1234

2 blocks:

123.4, 

124.3, 

134.2, 

1.234, 

12.34, 

13.24, 

14.23

3 blocks:

1.2.34, 

1.24.3, 

1.23.4, 

14.2.3, 

13.2.4, 

12.3.4

4 blocks:

1.2.3.4

I replied with a hint, saying, "This page explains what you need to do, once you reinterpret the Stirling recurrence as an enumeration." Only now, writing up this post, did I realize that I linked to the same page they were quoting from.

The key is in the sentence, "They satisfy the following recurrence relation, which forms the basis of recursive algorithms for generating them." Let's reinterpret the Stirling recurrence combinatorially. No wait, we don't need to. Wikipedia did it for us. Go read that first. If you didn't follow Wikipedia's explanation, here's another angle:

Suppose you have a set of n elements, and you want to generate all the partitions into k blocks. Well, let's look at element n. What happens when you delete it from the partition?

One possibility is that n was in a block all by itself. After you remove it, you are left with a partition of n − 1 elements into k − 1 blocks. Therefore, to generate the partitions where n is in a block all by itself, you generate all the partitions of n − 1 elements into k − 1 blocks, and then tack on a single block consisting of just element n.

On the other hand, if element n was not in a block by itself, then removing it leaves a partition of n − 1 elements into k blocks. (Removing n did not decrease the number of blocks because there are still other numbers keeping that block alive.) Now, element n could have belonged to any of the k blocks, so you have k possible places where you could reinsert element n.

Therefore, our algorithm goes like this:

  • Handle base cases.
  • Otherwise,
    • Recursively call S(n − 1, k) and add element n separately into each of the k blocks.

    • Recursively call S(n − 1, k − 1) and add a single block consisting of just n.

Now that we spelled out what we're going to do, actually doing it is a bit anticlimactic.

function Stirling(n, k, f) {
 if (n == 0 && k == 0) { f([]); return; }
 if (n == 0 || k == 0) { return; }
 Stirling(n-1, k-1, function(s) {
  f(s.concat([[n]])); // append [n] to the array
 });
 Stirling(n-1, k, function(s) {
  for (var i = 0; i < k; i++) {
   f(s.map(function(t, j) { // append n to the i'th subarray
    return t.concat(i == j ? n : []);
   }));
  }
 });
}

You can test out this function by logging the results to the console.

function logToConsole(s) {
  console.log(JSON.stringify(s));
}

Stirling(4, 2, logToConsole);

Let's walk through the function. The first test catches the vacuous base case where you say, "Please show me all the ways of breaking up nothing into zero blocks." The answer is, "There is exactly one way of doing this, which is to break it into zero blocks." Math is cute that way.

The second test catches the other base cases where you say, "Please show me all the ways of breaking up n elements into zero blocks" (can't be done if n > 0, because you will always have elements left over), or you say, "Please show me all the ways of breaking up 0 elements into k blocks" (which also can't be done if k > 0 because there are no elements to put in the first block).

After disposing of the base cases, we get to the meat of the recurrence. First, we ask for all the ways of breaking n - 1 elements into k - 1 blocks, and for each of them, we add a single block consisting of just n.

Next, we ask for all the ways of breaking n - 1 elements into k blocks, and for each of them, we go into a loop adding n to each block. The goofy map creates a deep copy of the array and adds n to the ith block.

Here's a walkthrough of the goofy map:

  • The concat method creates a new array consisting of the starting array with the concat parameters added at the end. If a parameter is an array, then its elements are added; otherwise the parameter itself is added. For example, [1].concat(2, [3, 4]) returns [1, 2, 3, 4]. The concat method creates a new array, and a common idiom is s.concat() to make a shallow copy of an array.

  • The map method calls the provided callback once for each element of the array s. The return values from all the callbacks are collected to form a new array, which is returned. For example, [1,2,3].map(function (v) { return v * 2; }) returns the new array [2, 4, 6].

  • The map callback is called with the subarray as the first parameter and the index as the second parameter. (There is also a third parameter, which we don't use.)

  • Therefore, if all we want to do was create a deep copy of s, we could write s.map(function (t, j) { return t.concat(); }).

  • But we don't want a perfect deep copy. We want to change the ith element. Therefore, we check the index, and if it is equal to the i, then we append n. Otherwise, we append [] which appends nothing.

  • After building the array (with modifications), we pass it to the callback function f.

This pattern is common enough that maybe we should pull it into a helper function.

function copyArrayOfArrays(array, indexToEdit, editor) {
 return array.map(function(e, i) {
  return i === indexToEdit ? editor(e) : e.concat();
 });
}

function Stirling(n, k, f) {
 if (n == 0 && k == 0) { f([]); return; }
 if (n == 0 || k == 0) { return; }
 Stirling(n-1, k-1, function(s) {
  f(s.concat([[n]])); // append [n] to the array
 });
 Stirling(n-1, k, function(s) {
  for (var i = 0; i < k; i++) {
   f(copyArrayOfArrays(s, i, function(e) { return e.concat(n); }));
  }
 });
}

The copy­Array­Of­Arrays function abstracts the goofy map: You give it an array of arrays, and optionally an index to edit and the function that does the editing. It copies the array of arrays and calls your editor on the element you want to edit.

To reduce the number of memory allocations, the recursion could also be done destructively. You're then counting on the callback not modifying the result, since you're going to use it again.

function Stirling(n, k, f) {
 if (n == 0 && k == 0) { f([]); return; }
 if (n == 0 || k == 0) { return; }
 Stirling(n-1, k, function(s) {
  for (var i = 0; i < k; i++) {
   s[i].push(n);
   f(s);
   s[i].pop();
  }
 });
 Stirling(n-1, k-1, function(s) {
  s.push([n]);
  f(s);
  s.pop();
 });
}

The original question was about enumerating all partitions (Bell numbers), and that's easy to put together from the Stirling numbers.

function Bell(n, f) {
 for (var i = 1; i <= n; i++) {
  Stirling(n, i, f);
 }
}
Comments (15)
  1. Brian_EE says:

    Maybe now they can update the link at the bottom of their page for the C program to link to this article. theory.cs.uvic.ca/…/distribute.pl.cgi

  2. The link to A000110 (from the "Info about Set Partitions" page) is broken: here's the correct link

    oeis.org/search

  3. Nitpick: your Bell() function's for loop should start at i = 0 rather than i = 1, to catch the Stirling(0, 0, f) case.

  4. GWO says:

    There's something about that algorithm that screams "Write me in lisp"!

    (Note to young people: lisp is what Haskell will look like when it eventually evolves into a useful programming language)

  5. silly says:

    (((Note) (to young people)): (lisp ((((is what Haskell) (will look like) (when it eventually evolves) (into a useful programming language))))))

    FTFY stackoverflow.com/…/235790 :)

  6. AC says:

    >lisp

    >look like

    >useful programming language

    I like functional programming like the next of you, but seriously, the single worst thing about lisp is how it LOOKS (or reads).

    >Lisp=Lotsa insignificant Stupid Parentheses

  7. Neil says:

    I noticed some potential optimisations:

    n < k (no results)

    n == k (n blocks each with one element)

    Having dealt with all of the n == 0 cases you can also cover:

    k == 0 (no results)

    k == 1 (one block with all n elements)

  8. Arakula says:

    "Back in 2005"?

    Well, I'm a firm believer in procrastination, too, but I don't think I got anything on my backlog that's been sleeping there for 9 years… I bow my head in admiration :-)

  9. GWO says:

    @AC Fair point – although I meant "look" somewhat more figuratively than literally. i.e. "Lisp has developed a balance between the imperative and the functional which Haskell will probably eventually emulate." [I do appreciate there is no one thing called "lisp", and that each sub-lisp has itself struck this balance in a difference place]

    See also en.wikipedia.org/…/Greenspun%27s_tenth_rule

  10. acq says:

    Wow Raymond uses JS to present Haskell-like programs.

  11. Nick says:

    Turns out JavaScript is actually a pretty cool language that lets you do some pretty neat things.

  12. Dave Bacher says:

    That JavaScript doesn't pass coding standards because it is comprehensible.  

    First, run each word in the routine names through a thesaurus and pick the best and most incomprehensible synonym.  Then, remove such minor letters as e.  After that, introduce at least three spelling errors in each word.  To be cool, also replace all c's with k's, and all k's with c's.  If there's an f, that becomes ph and so forth.

    Instead of using separate functions — use one function, pass it a parameter that indicates which work to do.  Don't make the mistake of doing all the related work together, instead intermix the lines with an if statement checking which work to do on a line by line basis.  The JavaScript console is for the weak, so instead use jQuery and post to Google Docs or Office Online.  In addition be cautious to avoid the error of using asynchronous requests, because nothing signals fantastic JavaScript like the browser hanging while it is running.

    If possible, name your function $ as that is sure not to collide with anything else on the page.

    Now you have proper JavaScript code.

    All kidding aside, it's an elegant solution to the problem though.

  13. Gabe says:

    Nick: Raymond's JS code is actually pretty straightforward to translate into C#. Just add some types, change the spelling of "concat" to "Concat" and "map" to "Select", and change the "function" syntax, and it works.

  14. Ralph says:

    I like the use of javascript here, opening a fresh tab in my browser and bringing up its console is a very quick way of writing/testing a quick function like this one.

Comments are closed.

Skip to main content