Arbitrary-length analogs to de Bruijn sequences

Abstract

Let $\tilde{\hat{I}}\pm$ 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 $\tilde{\hat{I}}\pm$ is $\lfloor L/K^m\rfloor$ or $\lceil L/K^m\rceil$. When $L=K^N$ for any positive integer $N$, $\tilde{\hat{I}}\pm$ is a de Bruijn sequence of order $N$, and when $L\ne K^N$, $\tilde{\hat{I}}\pm$ shares many properties with de Bruijn sequences. We describe an algorithm that outputs some $\tilde{\hat{I}}\pm$ for any combination of $K\ge 2$ and $L\ge 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.

18 pages, 3 algorithms, 1 table; v2 refines language and fixes references