How to generate all distinct cyclic binary strings of a certain length?

Question

I'm looking for a way to generate all cyclic/reflective distinct binary strings of a certain length with equal $0$s and $1$s. That is, a string $s_1$ would considered identical to some other string $s_2$ if:

• $s_1$ is a cyclic shift of $s_2$, e.g. $1000 = 0100$
• $s_1$ is a mirroring of $s_2$, e.g. $101100 = 001101$
• $s_1$ is a cyclic shift of a mirroring of $s_2$, e.g. $101100 = 100110$

I wrote a quick script to detect these and got the following (for even numbers):

4: 1100 1010

6: 010101 001011 000111

8: 11110000 11101000 11100100 11011000 11010100 11010010 11001100 10101010

Is there a name for this set ? Is there a way of quickly generating it?

Answer 1

These are $2n$-bead black-white reversible necklaces with $n$ black beads, and they are enumerated by sequence A005648 in the On-Line Encyclopedia of Integer Sequences. The following formula is given for the number of necklaces:

$$a(n) = \left[\frac{1}{4n} \sum_{d|n} \phi(n/d)\,\binom{2d}{d}\right] + \frac12\binom{2k}{k}$$ where $k = \lfloor n/2\rfloor$.

The following Python code generates these necklaces.

from itertools import combinations, chain
import numpy as np

def binary_words(zeros, ones):
    n = zeros + ones
    for c in combinations(range(n), ones):
        word = np.zeros(n, dtype=int)
        word[list(c)] = 1
        yield tuple(word)

def cyclic_permute(word):
    for i in range(len(word)):
        yield word[i:] + word[:i]

def dihedral_permute(word):
    return chain(cyclic_permute(word), cyclic_permute(word[::-1]))

def is_reduced(word):
    return all(word <= w for w in dihedral_permute(word))

def balanced_necklaces(n):
    return list(filter(is_reduced, binary_words(n, n)))