Dyck Words & Catalan Numbers

I recently watched a Numberphile video on the Catalan series, which happens to count lot of different things, from partitions of sets, to divisions of polygons, to unique binary trees of a certain order. The video is fascinating and well worth a watch.

One other thing the Catalan numbers count is the number of possible Dyck words of a given semi-length. A Dyck word is a word in a binary (having two elements) alphabet, where no prefix of the word has more of the second element than the first. That's the complicated definition. The simple definition is a balanced set of parentheses, like so: "()()(())" or "((()))()". This should jump out as interesting to any developer - we use parentheses all day!

So, the Catalan numbers count the Dyck words of a given semi-length. For example, there are 42 Dyck words of semi-length 5, since the fifth Catalan number is 42. But how can we generate them all? And more importantly, how can we do it..... in Rust?

It turns out that defining the Catalan numbers and Dyck words in terms of recursion is easy. But with recursion, there's a limit to how far our program can go. Eventually, the call stack won't be able to hold all our recursive function calls, and our program will terminate with a stack overflow. Even if we use the heap with more advanced features, we will slowly eat into memory and run up against the computer's physical limits. (In my case, this is 24 GiB of DDR3 in a mobile workstation from 2013.)

We need a better algorithm than the recursive solution. We need a perfect algorithm.

...and there is one! It is entirely possible to convert recursive definitions and functions into iterative ones, and someone (Dr. Knuth, it seems) has already done so for this particular problem. After a bit of digging, I was able to find a paper on the subject.

The algorithm goes as close as possible to the metal by representing opening parentheses as a 1 bit, and closing parentheses as a 0 bit. In the abstract you can see the algorithm in C-like pseudo-code. It's simply bitwise integer math. Fast, efficient, loop-less, and branch-less. The only trick is that it requires the "previous" Dyck word to act upon.

You can generate the "next" Dyck word in the sequence by flipping pairs around. Taking the Dyck word of the form "()()()()()()" or "101010101010" to be the least, and the word of form "(((((())))))" or "111111000000" to be the greatest, we can run this algorithm on its output until we reach the greatest Dyck word of the given semi-length. The integer passed in to the algorithm must represent a valid Dyck word, or it's a precondition violation.

The full source of my program is here, but I'll reproduce the Rust port of the algorithm below.

fn next_dyck_word_bin(w: u64) -> u128 {
    // Calculate a, potentially using two's complement for negation.
    let a = w & (!w + 1);

    // Calculate b directly.
    let b = w + a;

    // Calculate c using bitwise XOR.
    let c = w ^ b;

    // Shift c right by 2, ensuring unsigned division.
    let c = (c as u128 / a as u128) >> 2; // Cast to u128 for division.

    // Add 1 to c, handling potential overflow.
    let c = c.wrapping_add(1);

    // Apply mask and bitwise OR with b.
    let mask = 0xaaaa_aaaa_aaaa_aaaa_aaaa_aaaa_aaaa_aaaa; // I think this is long enough...

    // Return the resulting Dyck word as a u128.
    ((c * c - 1) & mask) | b as u128
}

I've run the program for semi-length 20, whose Catalan number is 6,564,120,420. As you can see, the series grows quickly. It ran for 6.5 hours before I terminated it; the output file had reached ~200 GiB and over 4 billion of the 6.5 billion Dyck words, represented as ones and zeroes. But in that time, my memory usage never wavered, and my CPU stayed locked at 100%. It was very interesting to watch in reality what O(1) means - it's an invincible algorithm.

A couple improvements to the rest of the program have been suggested to me; I'll implement them soon. Next, I want to work on some numerical integration techniques, like Simpson's method. This was an exciting peek into the world of combinatorics and theoretical computer science. I'm excited to see more!