De Bruijn Sequence and Universal Cycle Constructions

Decoding the Granddaddy Output
Algorithm
Order $n$
Alphabet size $k$
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 $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 then it has rank $k^n$. Unranking is the process of determining the string $\alpha$ in $D$ starting at index $r$ (the rank of $\alpha$).

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

0000001000011000101000111001001011001101001111010101110110111111

The string $\alpha = 010101$ has rank 47.

The only DB sequence construction presented in this project that has an efficient (polynomial-time) 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]. The algorithms are based on efficient ranking algorithms for necklaces and Lyndon words. The only other known efficient decoding algorithms are for inter-leaved or inductive constructions [MEP96,Tul01]. Further background on other (inefficient) decoding methods is given in [MEP96].
Download source code

» C program

References

  • [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