CLR cover

Additional Problem 13: Ring Sequences (Preliminary version)

It is very simple to construct a word of length $n\le 2^k$ such that all its $k$-factors are distinct: we can take a prefix of de Bruijn word of rank $k$.

The difficulty grows substantially when we require that all cyclic $k$-factors are distinct. Such words of length $n$ were called $(k,n)$-ring sequences in [Yoeli 1962]. Of course we should have $1\le n\le 2^k$.

Design a linear time algorithm constructing a binary $(k,n)$-ring sequence, for given $n,k$ such that $1\le n\le 2^k$.

References