CLR cover
Previous problem

Problem 128: Words with distinct cyclic k-factors

Next problem
\( \)

Assume the alphabet is $\{0,1\}$. A binary word $v$ is called a cyclic factor of a word $w$, if $v$ is a (standard) factor of $w^{\infty}$. A binary (cyclic) word $w$ of length $k\leq n\le 2^k$ is called a $k$-ring word if each cyclic $k$-factor of $w$ occurs once. Observe that string of length $k$ is a $k$-ring if and only if it is primitive.

We refer Problem 18, Problem 69 for the definition of de Bruijn graph $G_{k}$. Two edges of $G_{k}$ are loops and in this problem we disregard these two edges. The nodes of $G_{k}$ are binary words of length $k-1$, and edges correspond to words of length $k$. The number of edges of $G_k$ is $2^k$. The size of these graphs is $O(n)$ since we can choose minimal $k$ such that $n\le 2^k$. A closed chain (c-chain, in short) is a path $C$ ending and starting in the same node and containing each of its edges exactly once. Denote by $w=\RingWord(C)$ a word $w$ resulting by spelling labels of consecutive edges of $C$.

Design a linear time algorithm constructing a binary $k$-ring word, for given $n,k$ such that $k\le n\le 2^k$.
Equivalent formulation: construct a closed chain $C$ of length $n$ in $G_k$ (then $\RingWord(c)$ is a $k$-ring word of length $n$).

References