Generate necklaces, Lyndon words and other objects with equivalence under rotation of length $n$ over the alphabet $\{0,1,\ldots,k-1\}$. The case $k=2$ are bitstrings.
A
necklace is an equivalence class of $k$-ary strings under rotation. We take the lexicographically smallest such string as the representative of each equivalence class and use this in the output of the program.
A
Lyndon word is an aperiodic necklace representative.
Unlabelled necklaces are an equivalence classes of necklaces under permutation of alphabet symbols. Note that by permuting the alphabet symbols of a necklace and then rotating the string into its lexicographically smallest position, the result is a necklace representative.
Among all permutations of alphabet symbols that resulting necklace that is lexicographically smallest is used as the representative of an unlabelled necklace.
For example, here is an equivalence class of unlabelled ternary necklaces: $\{011222, 022111, 001112, 002221, 000122, 000211\}$. The lexicographically smallest of these is $000122$ and so it is chosen as the representative.
For information on generating necklaces and Lyndon words and their unlabeled counterparts in constant amortized time see [CRS+00].
In many applications not all necklaces are required, but only those of fixed density, meaning that the number of non-zero entries is fixed.
In the more general case, one may want a list of necklaces with fixed content where the number of occurrences for every character is fixed.
For information on generating necklaces with fixed content and fixed density in constant amortized time see [Saw03] and [RS99].
Necklaces that do not contain a specified sequence as a substring are known as necklaces with forbidden substrings.
For example, when considering all necklaces with $n=4$ and $k=2$ with the restriction that there are no $00$ substrings we get the set: $\{0101, 0111 ,1111\}$.
For more information on generating necklaces with forbidden substrings see [RS00].
A bracelet is a necklace that can be turned over.
For information on generating bracelets in constant amortized time see [Saw01].
For bracelets with fixed content see [KSAH13].
The number of nonisomorphic unit interval graphs is the same as the number of binary bracelets of length $2t-1$ with content $(t,t-1)$.
A charm bracelet is a generalization of a bracelet considering the action of the group of affine transformations $j \mapsto a+dj\pmod n$ on the indices.
For more information see [ĐKRS15].
A chord diagram is a set of $2n$ points on an oriented circle (counterclockwise) joined pairwise by $n$ chords.
For information on efficiently generating all chord diagrams with $n$ chords see [Saw02].
We encode such a diagram by walking around the circle, and for each point we record the number of forward steps (in counterclockwise direction) to reach its partner along the same chord.
For instance, for $n=3$ the diagram with three chords on the convex hull is encoded by 151515.
Lyndon brackets correspond to the basis of the $n$th homogeneous component of the free Lie algebra.
For information on generating such a basis in $O(n)$ time per element see [SR03].
Links to the binary objects in the Online Encyclopedia of Integer Sequences:
Enumeration formulae for $k$-ary necklaces and $k$-ary Lyndon words:
\[N_k(n) = \frac{1}{n} \sum_{d\vert n} \varphi(d)k^{n/d}, \qquad L_k(n) = \frac{1}{n} \sum_{d\vert n} \mu(d)k^{n/d}.\]
Enumeration formula for $k$-ary bracelets:
\[
B_k(n) = \left\{ \begin{array}{ll}
\frac{1}{2} N_k(n) + \frac{1}{4}(k+1)k^{n/2} & \text{ if $n$ is even,} \\
\frac{1}{2} N_k(n) + \frac{1}{2}k^{(n+1)/2} & \text{ if $n$ is odd.}
\end{array} \right.
\]
The number of nonisomorphic unit interval graphs is the same as the number of bracelets with $n$ black and $n-1$ white beads.
Enumeration formula for binary unlabeled necklaces:
\[U_2(n) = N_2(n) - \frac{1}{2n} \sum_{\text{odd } d\vert n} \varphi(d)2^{n/d}.\]
Enumeration formula for chord diagrams:
\[
C(n) = \left\{ \begin{array}{ll}
\frac{1}{2n} \displaystyle{\sum_{pq=2n} \varphi(p)p^{q/2}(q-1)!!} & \text{ if $p$ is odd,} \\
\frac{1}{2n} \displaystyle{\sum_{pq=2n} \varphi(p)\sum_{j=0}^{\lfloor q/2 \rfloor}{q \choose 2j}(2j-1)!!} & \text{ if $p$ is even.}
\end{array} \right.
\]
Enumeration formula for $k$-ary necklaces with fixed content:
\[N_k(n_1,n_2,\ldots, n_k) = \frac{1}{n} \sum_{j \vert \gcd(n_1,n_2, \ldots, n_k)} \varphi(j)\frac{(n/j)!}{(n_1/j)!(n_2/j)!\cdots (n_k/j)!}.\]
When $k=2$, the above formula can be applied and simplified for the case of binary fixed-density necklaces.