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?

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in combinatorics, computation and tagged , , , , , , , , , , , . Bookmark the permalink.

1 Response to Efficiently listing orthobraces

  1. Pingback: Why drawing orthogons is hard | The Math Less Traveled

Comments are closed.