Arbitrary-length analogs to de Bruijn sequences

Let $\widetildeα$ be a length-$L$ cyclic sequence of characters from a size-$K$ alphabet $\mathcal{A}$ such that the number of occurrences of any length-$m$ string on $\mathcal{A}$ as a substring of $\widetildeα$ is $\lfloor L / K^m \rfloor$ or $\lceil L / K^m \rceil$. When $L = K^N$ for any positive integer $N$, $\widetildeα$ is a de Bruijn sequence of order $N$, and when $L \neq K^N$, $\widetildeα$ shares many properties with de Bruijn sequences. We describe an algorithm that outputs some $\widetildeα$ for any combination of $K \geq 2$ and $L \geq 1$ in $O(L)$ time using $O(L \log K)$ space. This algorithm extends Lempel's recursive construction of a binary de Bruijn sequence. An implementation written in Python is available at https://github.com/nelloreward/pkl.

No reviews yet.

No comments yet.