De Bruijn Sequence and Universal Cycle Constructions

Decoding the Granddaddy Output
Algorithm
Order $n$
Symbols $k$
Lower bound on weight $w$
String over $\{0,1,\ldots, k{-}1\}$
Decoding (ranking/unranking) the Granddaddy DB sequence

Given a DB sequence $\mathcal{D}$ of order $n$, the rank of a string $\alpha$ (of length $n$) is the starting index where $\alpha$ appears in $\mathcal{D}$. If $\alpha$ is a prefix of $\mathcal{D}$, then it has rank 1. If $\alpha$ starts at the last symbol of $\mathcal{D}$ and wraps around to the beginning, then it has rank $k^n.$ Unranking is the inverse process: given a rank $r$, it determines the string $\alpha$ that starts at index $r$ in $\mathcal{D}$.

Example  

Consider the Granddaddy DB sequence for $n=6$ and $k=2$:

      0000001000011000101000111001001011001101001111010101110110111111.

The string $\alpha = 100001$ has rank 7.

The only DB sequence construction presented in this project that has a space-efficient decoding algorithm is the Granddaddy [KRR16,SW17]. The ranking requires $O(n^2)$-time and the unranking requires $O(n^3 \log k)$-time (unit-cost RAM model) in the provided implementation based on [SW17]; they require $O(n^2)$ space. The algorithms are based on efficient ranking algorithms for necklaces and Lyndon words. This algorithm is the key to solving Project Euler Problem 941.

The only other space-efficient decoding algorithms are based on a recursive construction applying Lempel's homomorphism [MEP96,Tul01], although, they do not handle the cases when $k$ is an odd prime and $n$ is odd. When $k=2$, Knuth describes efficient decoding algorithms (based on [Tul01]) on pages 697-699 in answer to exercises 97-99 on p.317 [Knu11].

Bounding the weight

By restricting the Granddaddy concatenation construction to necklaces with weight at most $w$, we obtain a bounded-weight de Bruijn sequence. This sequence can also be ranked and unranked in polynomial time [GIJS26]. By considering its complement, where each symbol $x$ is replaced with $(k-x)$, we obtain a bounded weight de Bruijn sequence with an upper bound on the weight that can apply the same decoding routines. This decodable sequence can also be applied to decode universal cycles for $t$-subsets and $t$-multisets.

Download source code

» Granddaddy C program

» Bounded weight Granddaddy C program

References

  • [GIJS26] D. Gabric, W. Imam, L. Janik-Jones, and J. Sawada. Decoding universal cycles for $t$-subsets and $t$-multisets by decoding bounded-weight de Bruijn sequences, manuscript 2026.

  • [Knu11] D. E. Knuth. The Art of Computer Programming. Vol. 4A. Combinatorial Algorithms. Part 1. Addison-Wesley, Upper Saddle River, NJ, 2011.

  • [KRR16] T. Kociumaka, J. Radoszewski, and W. Rytter. Efficient ranking of Lyndon words and decoding lexicographically minimal de Bruijn sequence. SIAM J. Discrete Math, 30(4):2027-2046, 2016.

  • [MEP96] C. Mitchell, T. Etzion, and K. Paterson. A method for constructing decodable de Bruijn sequences. IEEE Transactions on Information Theory, 42(5):1472-1478, 1996.

  • [SW17] J. Sawada and A. Williams. Practical algorithms to rank necklaces, Lyndon words, and de Bruijn sequences. Journal of Discrete Algorithms, 43:95-110, 2017.

  • [Tul01] J. Tuliani. De Bruijn sequences with efficient decoding algorithms. Discrete Mathematics, 226(1):313-336, 2001.

Interested in generating other combinatorial objects? Visit http://combos.org