## Efficiently listing orthobraces

In my last couple posts, we talked about a simple yet inefficient method for listing all orthobraces of a particular size. So how do we generate them efficiently? It turns out that it can be done: in 2011, Karim, Sawada, Alamgir, and Husnine published a paper entitled Generating Bracelets with Fixed Content which gives us exactly what we need to generate orthobraces efficiently. Unfortunately, the algorithm is rather complicated, and the proof that it works is more complicated still! (Perhaps I will write about it someday, but that would be another many-post series in and of itself!) But I implemented it here (in Haskell), and used it to generate the pictures in my original post.

In one sense, I don’t know why I’m writing about this: it’s more complicated than I’m willing to explain at the moment, and actually it makes little practical difference anyway, because the naive code from my previous post can generate, say, all $3260$ orthobraces of length $20$ in 1.3 seconds—plenty fast enough for practical purposes, and we can’t reasonably expect to draw or look at more than $3000$ of these things. I just think it’s cool that a simple question like this turns out to have a very nontrivial answer, and someone has answered it—but only quite recently! (Incidentally, for comparison, the efficient code generates all $3260$ orthobraces of length $20$ basically instantaneously, in 0.03 seconds.)

In an upcoming post or two, I’ll explain the remaining missing piece: how do we go from an orthobrace to a picture of an orthogon?