Nested sets of pairs, twenty-four years later

There is a directory on my disk called nsp-ncp. It holds nine C programs that were meant to do the same thing, seven more in C++, two Visual Basic projects, a handful of Word documents in Greek and two papers in PostScript. Today I pointed Claude Code at it and asked for three things; pick the best of the C programs and make a repository out of it, give it a page on this site, and write this post. I added, helpfully, that the one in nsp-ultra-fast was probably the fastest.

It is not. The function in it that was supposed to do the work is while(1){}, and it never got any further than that (it is, I suppose, the fastest of the lot at doing nothing :) ).

Before going on, who did what. The algorithm is twenty-four years old, and it belongs to my friend Kostas Manes and me; the ranking further down is his alone. Everything written in 2026 (the C, the tests, the measurements, and the checks against our old notes) was done by the model, in one session. My part was the request, and then reading what came back. So this post is about two things: what we worked out in 2002 and 2004, and what the model found when it read it.

Nested sets of pairs

Put 2n points on a line and join them two by two with arcs drawn above it, so that no two arcs cross. That is a nested set of pairs, an NSP in our notes, and in the spring of 2002 it was what Kostas and I were studying. Read the points from left to right, write an opening bracket where an arc starts and a closing one where it ends, and you get a Dyck word; n opening and n closing brackets, arranged so that no prefix closes more than it has opened. The set {1,4} {2,3} {5,6} is (())().

How many are there? C_n = (2n)! / ((n+1)! n!), the Catalan numbers, which go 1, 2, 5, 14, 42, 132 and then grow by a factor of almost four at every step. They count a surprising number of other things too (binary trees, triangulations of a polygon, the ways to put brackets in a product), and one of them mattered to us; the non-crossing partitions of n points, which I will come back to.

The trick that made it a programming problem is in Kostas's notes of March 2002. Write ( as 1 and ) as 0, and a Dyck word becomes an even number: ()()() is 101010, which is 42, and ((())) is 111000, which is 56. Listing every nested set of size n becomes listing the numbers whose binary digits form a Dyck word, in increasing order, and that is lexicographic order: 42, 44, 50, 52, 56 for n = 3. The same notes do the listing with arithmetic (to move a 1 one place to the left you add 2^A, where A is its position), they write every word as a recurrence on the one before, and his Visual Basic program of June 2002 does exactly that.

Shift and push

The version that lasted keeps the positions of the 1s instead of the number. Every opening bracket has a home, its place in the smallest word ()()…(), and it can only move left of it, never onto the bracket before it. Moving any of them left makes the word bigger. So the next word always comes from one of two moves, and Kostas named them in his C++ of 2004:

• Shift. If the last opening bracket has room, move it one place to the left.
• Push. If it has not, walk left along the run of adjacent brackets it ends until one has room, move that one a place to the left, and send every bracket after it back home. If none has room, the word was ((…)), the last.

()()()   1 3 5   shift: 5 to 4
()(())   1 3 4   push:  4 is against 3, so 3 moves to 2 and the last goes home to 5
(())()   1 2 5   shift: 5 to 4
(()())   1 2 4   shift: 4 to 3
((()))   1 2 3   push:  nothing has room, so the list is done

That is the whole algorithm. The push looks expensive, because it can walk the entire word, and here the model found something that is not in our notes. A word needs a push exactly when its last two opening brackets are adjacent, and those words pair off one to one with the Dyck words of length 2(n−1); remove one of the two brackets and one of the closing brackets after them, and you get every smaller word exactly once. So the push runs C_n−1 − 1 times and the shift C_n − C_n−1 times. For n = 18 that is 129,644,789 pushes against 347,993,910 shifts, and it counted them to make sure.

There is a fourteen-line program in the directory, catalan-rate, built on 26 August 2004, that prints (4n+2)/(n+2) for every n up to its argument. That is C_n+1/C_n, so somebody (me, presumably) wanted to know how fast the thing grows. It tends to 4. It is the same 4 that makes three words in four a shift, and the reason every extra n costs four times as much as the one before.

Kostas's ranking

The rank of a word is its place in the list. In July 2004 Kostas wrote a note, simply called RANKING, with a C++ program beside it, that computes the rank without walking the list. Number the opening brackets from the right this time, and say the i-th is moved k when it sits k places to the left of its home. Then let d(i, k) be the number of words that come before the first word in which the i-th bracket is moved k. His note derives

d(i, 0) = 0
d(i, 1) = C(i)
d(i, k) = d(i+1, k-1) - d(i+1, k-2)

and the rank of a word is 1 plus d(i, k) summed over its brackets, each with its own k. Unranking runs the same sum backwards. The note prints the table for n = 10 and observes that its diagonal adds up to 16,795, which is C₁₀ − 1; the rank of (((((((((()))))))))), less the 1 the count starts from.

One step of the derivation carries the remark να δειχθεί, to be shown. The model did not prove it either. It did the next best thing for a step like that; it checked it, against the list itself, for every word up to n = 12, and it held. On the way it noticed that the table is Catalan's triangle, d(i, k) = k/(i+k) · binomial(2i+k−1, i), and checked that for every entry up to n = 36. The program does not use the closed form. It fills the table with Kostas's recurrence, because that is the method, and the method is his.

Partitions, two letters at a time

Most of the pages in Kostas's notes are about another correspondence, between nested sets of pairs and the non-crossing partitions of n points (split 1..n into blocks, so that no two blocks cross when drawn as arcs). The construction in the notes is a geometric one. Shade the regions under the arcs alternately, starting under each outermost arc, and put a point in every gap between neighbouring points. The notes prove that the shaded gaps are always (1, 2), (3, 4) and so on up to (2n−1, 2n), so there are always n of them, and two of those points belong to the same block when they sit in the same shaded region. The figure at the top does it for (((())))(), which gives {1,4} {2,3} {5}.

It is a nice proof and a lot of drawing. The program does it by reading the word two letters at a time, and so did Kostas's summary of where we stood (a document called, I am not making this up, Summary_for_Bill.doc; I am the Bill), where the pairs of letters are digits of a number in base 4:

• (( opens a block;
• )( joins the innermost open block, which stays open;
• )) joins it and closes it;
• () is a block of its own.

The model checked the two-letter reading against the shading for every word up to n = 9, and the notes give all fourteen partitions for n = 4; dyck -f ncp 4 prints the same fourteen, in the same order. That part of the 2002 work holds.

The part that never got finished is the one the summary leaves open. Draw one nested set above the line and another below it, and sometimes the two close into a single curve, a closed meander; the summary calls that the matching property. Kostas's Visual Basic program could list the matchings of a given set (for one set of eight pairs it reports 90 of them, in three seconds). What the summary asks for, and does not have, is a condition you can read off the two words, and it says so plainly: "the exact necessary and sufficient conditions remain unknown". There is also a C program in the directory, meander-matching, that reads its input file and stops. As far as I know, nobody has a formula for the number of meanders today either.

Twenty-two years of hardware

The timings from 2004 are in the directory too; Kostas's on a 2.4 GHz Celeron, counting only, and mine for nsp-classic writing every word to disk. The model compiled both programs again, with a current compiler, and ran them next to the new one on my M4 Max:

Twenty-two years of hardware bought about twenty-five times, on an algorithm that did not change at all. At four times the work per step, that is a little over two more n in the same afternoon; n = 20 is 6,564,120,420 words and takes eight and a half seconds to count, n = 30 would take about two months.

The other column is the one I did not expect. The new program writes words four and a half times faster than nsp-classic (it changes two letters per word, where nsp-classic spelled every word out from scratch), but it is slower at counting than the code we wrote in 2004. I was a bit disappointed, but the reason is fair. Our 2004 counters never spelled a word at all; they moved positions and added 1 to a double. The new one keeps the word spelled out at every step, because that is what its count is meant to time.

What the model did

It read everything first. The C and C++ were easy; the Word files needed textutil, and the comments in Kostas's C++ were in Greek, in the Windows-1253 code page, so it converted those too. The copies on my disk all say 2016, so it dated the files from what is inside them; the build time in the header of each Windows executable, and the dates and authors that Word keeps in every document. That is how I know that Kostas's first notes are from March 2002, and that nsp-fast was built on 17 August 2004, the same afternoon he last saved starting_set_shift_push.cpp. Then it compared the two and concluded that they were the same algorithm, once in C and once in C++.

Before writing a line of C, it checked our mathematics in Python. The enumeration against a brute-force sort, the ranking against the list, the two-letter partitions against the shading; all of the checks above came from that pass. Then it wrote the program, and for a reference it did not use its own Python. It compiled my nsp-classic from 2004 and compared the outputs, byte for byte, for every n from 1 to 15 (the last one is 300 MB). They are identical. The tests in the repository keep the checksums of the old program's output, so that the comparison survives without the old code.

It also found the one thing in our programs that has aged badly. We stopped when a counter reached C_n, computed from factorials in a double. Compiled today, that value is inexact from n = 14 on, which is harmless while it rounds down; at n = 24 it rounds up, and nsp-classic would write one word too many, the first word all over again. Nobody would have noticed, at sixty-three terabytes of output.

And it made mistakes, which I found more instructive than the rest. Its first benchmark said the new program was thirty times slower than the old one. It did not believe it, and it was right not to; my shell is zsh, and zsh had quietly copied the program's output into the pipe that was meant to carry only the timing, so it had been measuring awk reading gigabytes of brackets. Later it wrote in the README that the compiler folds our old counting loop into a single addition, then went and read the disassembly, found a floating-point add for every word, and took the sentence out. It also broke its own code on purpose, four times, to see whether the tests noticed (they did, every time). That is what I would ask of a colleague, and I would not always get it.

Epilogue

So what did twenty-four years change? The algorithm, not at all; the shift and the push are exactly what they were in August 2004, and the ranking is Kostas's recurrence, entry for entry. What changed is everything around it. In 2004 our test was that the count came out as a Catalan number, and the Catalan number came out of a double. Now there are checksums, a reference, a separate implementation in another language, and a test suite that has been shown to fail.

And there is the question of who keeps it. For twenty years this existed as a directory on my disk (notes in Greek, in Word, and programs for Dev-C++ and Visual Basic), and as a 2008 binary for a Mac that no Mac will start. It is now a repository that anyone can build in a second, with a README in English. The meanders are still where we left them. Maybe next time.

Reading

• The code: bkarak/dyck-words, MIT licensed, with the shift and push, the ranking, the five output formats and the tests.
• Its page on this site: Dyck Word Generator, with the 2008 page kept at the bottom.
• Jens Liebehenschel, Lexicographical Generation of a Generalized Dyck Language, and Ranking and Unranking of a Generalized Dyck Language, both from Goethe University Frankfurt. They were in the directory too, and they generalise all of this to more than one kind of bracket.