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?

Advertisements

About Brent

Assistant 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.

One Response to Efficiently listing orthobraces

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

Leave a reply. You can include LaTeX $latex like this$. Note you have to literally write 'latex' after the first dollar sign!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s