Circular Permutations

I was working on a new design and came up with an interesting math problem. Let’s say you have a hexagon split into three equal sections like this guy:

I have five colors in my game and wanted to make hexes that covered every combination. At first, that’s simple combinations: 5 choose 3 is 10, right? Well, no, because position matters. So it is all permutations of 3 elements of 5 without reuse is 5!/(5-3)! = 5x4x3 = 60, right? Well, not quite. Because if you rotate the image above it goes from {blue, red, yellow} to {yellow, blue, red} or {red, yellow blue} all of which can be covered by the same hex.

This is called circular permutation or necklace problems and apparently is a big thing in organic chemistry, which I thankfully never took. Apparently this is a nontrivial problem. I kept trying to do it the mathy way until pages started referencing Euler’s totient function, then I threw my hands up and did it with brute force since I only needed to solve my particular problem. It should be simple in my case, right? You start with 60 permutations and since you can rotate each hex twice, you can get rid of two-thirds of them? It’s just a matter of figuring out which ones.

So if you have a five item alphabet {a, b, c, d, e} and need all necklaces of length three, you get:

{a, b, c}
{a, b, d}
{a, b, e}
{a, c, b}
{a, c, d}
{a, c, e}
{a, d, b}
{a, d, c}
{a, d, e}
{a, e, b}
{a, e, c}
{a, e, d}
{b, c, d}
{b, c, e}
{b, d, c}
{b, d, e}
{b, e, c}
{b, e, d}
{c, d, e}
{c, e, d}

I don’t know if this will ever be useful to anyone else, but here you go.

Leave a Reply

Your email address will not be published. Required fields are marked *

Human? * Time limit is exhausted. Please reload the CAPTCHA.