Output | |||||||||
|
For some applications, a cycle of arbitrary length $1 \leq m \leq k^n$ is required such that every $k$-ary string of length $n$ appears at most once. For instance, consider trying to apply the de Bruijn Card Trick on a complete deck of 52 cards. We call such cycles cut-down de Bruijn sequences. They can also be thought of as universal cycles on a subset $\mathbf{S}$ of the $k$-ary strings of length $n$, where $|\mathbf{S}| = m$; however, the set $S$ is not known at the outset. The existence of such cycles for all $m$ was proved by Lempel [Lem71], and constructions for $k=2$ are given by Etzion [Etz86].
At a high-level, a cut-down DB sequence can be constructed in two steps:
More details along with an implementation to appear soon.