De Bruijn Sequences and Universal Cycles

Decoding the Granddaddy

Output

Algorithm
Order $n$
Symbols $k$
Rank ($1 \leq r \leq k^n$)
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 then it has rank $k^n.$ Unranking is the process of determining the string $\alpha$ in $\mathcal{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 = 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 crux 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].

Download source code

» C program

References

[Knu11] D. E. Knuth. The Art of Computer Programming. Vol. 4A. Combinatorial Algo- rithms. 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.

De Bruijn Sequence and Universal Cycle Constructions

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