Enumerating integer compositions (the return of the binomial coefficients)


In number theory, a composition of an integer is an ordered sequence of positive integers which sum to the target value. For example, the value 3 can be written as 3, 1+2, 2+1, or 1+1+1.

You can think about the target number as a string of stars, and a composition is a way of breaking the stars into groups. For example, here are the compositions of 3:

* * * 3
*|* * 1+2
* *|* 2+1
*|*|*   1+1+1

How would you generate all compositions of a particular length? In the above example, the compositions of length 2 would be 1+2 and 2+1. Let's take a look at the last star in the composition. If it is immediately preceded by a space, then removing it results in a string one star shorter, but with the same number of groups (but the last group is one star smaller). In other words, what's left behind is a composition of n − 1 of length k. You can recover the original string by adding a star at the end.

On the other hand, if the last star is immediately preceded by a vertical line, then removing it deletes an entire group, so what remains is a string one star shorter with one fewer group. In other words, what's left behind is a composition of n − 1 of length k − 1. You can recover the original string by adding a separator and a star at the end.

Therefore, our algorithm goes like this:

  • Handle base cases.
  • Otherwise,
    • Recursively call Compositions(n − 1, k) and add a star to the end. (I.e., increment the last term.)

    • Recursively call Compositions(n − 1, k − 1) and add a vertical line and a star to the end. (I.e., add a +1 to the end.)
function Compositions(n, k, f) {
 if (n == 0) { return; }
 if (k == 1) { f([n]); return; }
 Compositions(n-1, k, function(s) {
  f(s.map(function(v, i) { // increment the last element
    return i == s.length - 1 ? v + 1 : v;
  }));
 });
 Compositions(n-1, k-1, function(s) {
  f(s.concat(1)); // append a 1
 });
}

Compositions(5, 3, function(s) { console.log(s.join("+")); });

Once again, this algorithm should look awfully familiar, because we've seen it twice before, once in the context of enumerating subsets with binomial coefficients, and again when Enumerating bit strings with a specific number of bits set. All we're doing is decorating the results differently.

Here's a way to see directly how compositions are the same as subset selection. Let's ignore the stars and instead look at the gaps between them.

* * * * *
 ^ ^ ^ ^

Each of the gaps can hold either a space or a vertical line. Breaking n into k pieces is the same as drawing k − 1 vertical lines in the n − 1 gaps. In other words, you have n − 1 locations and you want to choose k − 1 of them: Ta da, we converted the problem into generating subsets of size k − 1 from a collection of size n − 1. (In mathematics, this visualization is known as stars and bars.)

Therefore, we could have made the Subsets function do the work:

function Compositions(n, k, f) {
 Subsets(n-1, k-1, function(s) {
  s.push(n);
  f(s.map(function(v, i) { return v - (s[i-1]||0); }));
  s.pop();
 });
}

The callback merely calculates the differences between adjacent elements of the subset, which is the number of stars between each line. There is a little extra playing around in order to create a virtual vertical bar at the beginning and end.

Since there is an incremental way of enumerating subsets, there should be an incremental way of enumerating compositions. If you look at how the incremental subset enumerator works, you can see how it maps to incremental composition enumeration: Incrementing an index is the same as moving a bar to the right, which maps to incrementing one term and decrementing the subsequent term. Resetting subsequent indices to the minimum values corresponds to setting the corresponding term to 1. The only trick is maintaining the value of the final term, which gathers all the values squeezed out of earlier terms.

function NextComposition(s) {
 var k = s.length;
 for (var i = k - 1; i >= 1; i--) {
  if (s[i] > 1) {
   s[i]--;
   s[i-1]++;
   for (; i < k - 1; i++) { s[k-1] += s[i] - 1; s[i] = 1; }
   return true;
  }
 }
 return false;
}

Exercise: If you wanted to generate all compositions of any length, you could do it by generating all compositions of length 1, then compositions of length 2, and so on up to length n. What's the easier way of doing it?

Bonus chatter: If you want to generate all partitions (which is like compositions, except that order doesn't matter), you can use this recursive version or this iterative one.

Comments (12)
  1. Yuri says:

    Does integer composition have any useful usage in the real world?

    [You must be new here. Monday programs do not come with motivation. -Raymond]
  2. Katie says:

    @Yuri

    According to Wikipedia "[integer partitions] occur in a number of branches of mathematics and physics," but there is no citation. I've done something similar but with factorization. It was a DSP application where breaking a high-order operation down into several lower-order passes could give huge performance gains, but there was no straightforward way of knowing the ideal order of each pass because the performance of each pass depended on the chain of previous pass orders. The number of passes involved was small enough that I could just brute-force the solution at the beginning of the task.

    Also, like Raymond says, we don't need motivation. :-) It's just a fun problem on its own.

  3. Yuri says:

    OK understood, it's just that I never experienced the 'fun with mathematics' part.

  4. Katie says:

    I think my favorite part of this series is that it clearly demonstrates how problems that seem different on the surface can actually be transformed between each other in straightforward ways. It isn't a skill that you always use in day-to-day programming, but when you get an interesting problem to work on being able to identify those connections can be invaluable.

    I've been tying together the fields of control systems and DSP in very powerful and novel ways with my current project, and it comes from recognizing similarities in the structures of the algorithms or the math behind them.

    [Recognizing how one problem can be transformed into another is important in software engineering. It lets you reuse code. -Raymond]
  5. Maurits says:

    >  for (i = k – 1; i >= 1; i–) {

    Gack! var this i, please; you can actually get away with this, but only once.

    [Fixed, but only once. -Raymond]
  6. Rick C says:

    @Maurits: Little Programs aren't polished.

  7. Jim says:

    "If you wanted to generate all compositions of any length … What's the easier way of doing it?"

    A composition can be identified by whether or not a break is present in each of the n-1 possible slots, as you said at the start. So just enumerate all numbers from 0 to 2^(n-1)-1 and consider the binary representation of each number as a composition.

  8. Neil says:

    I guess the ultimate limit of all these partitioning exercises is the problem of solving the Numbers game in Countdown. (Just for the record, the hardest problem that I have ever seen on the show was to compute 834 given 100, 75, 50, 25, 10 and 5.)

  9. John Doe says:

    @Neil, you can do it with only 100 and 10:

    (100*10 – 100 – 100) + (100/10 + 100/10 + 100/10) + (10/10 + 10/10 + 10/10 + 10/10)

    Obviously™, it gets cuter with the rest of the numbers:

    75*5 + 50*10 – 50 + 10 – 25/25

    Oh, the possibilities… Say, *that* would be an awesome little program!

  10. Katie says:

    @John Doe, you can't reuse the numbers. The goal is to get as close as possible, so something like 75*10 + 50 + 25 + 10 = 835 would be good, but there may be a way to reach it exactly.

  11. Katie says:

    rve.org.uk/countdown

    This finds the exact solution, but I can't imagine how anyone could figure it out in the game show situation.

  12. John Doe says:

    @Katie, Thanks.

    Sometimes, my hubris fogs me to the point I can't tell I'm stupid, much less how stupid I am.

Comments are closed.