Unique connections of N circularly-spaced points
This is written up pretty informally. It's based on some doodling at work, which turned into a morning of coding a few weeks ago.
The problem is this: How many unique ways are there to connect N evenly spaced points? By "unique" I mean not having any rotations or reflections in the set. Here's the full sets for order 1 to 4:
The code I wrote uses python's long integer and bit arithmetic code to figure out the sequence up to order 8:
1:1
2:2
3:4
4:19
5:136
6:3036
7:151848
8:16814116
Essentially, I represent each possible connection of N points as a binary number, then determine whether any of its reflections or rotations has a lower value. If any do, it's not the "canonical" version of that set, and it gets discarded. The problem with this approach, though I think it's the fastest, is that the time taken goes up very quickly. 8 took 6 hours or so to run, and checked 228 configurations. 9 would check 236 configurations and would therefore take about 64 days.
So that's as far as I'm likely to take this investigation. I'm writing it up here for general interest, and for other people to pick it up if they like.
PDF including Order 5
Python code
This entry was originally posted at http://cnoocy.dreamwidth.org/3312.html, where there are
comments. Please comment there using OpenID.