Abstract
A de Bruijn sequence is a binary string of length \(2^n\) which, when viewed cyclically, contains every binary string of length n exactly once as a substring. Knuth refers to the lexicographically least de Bruijn sequence for each n as the “granddaddy” and Fredricksen et al. showed that it can be constructed by concatenating the aperiodic prefixes of the binary necklaces of length n in lexicographic order. In this paper we prove that the granddaddy has a lexicographic partner. The “grandmama” sequence is constructed by instead concatenating the aperiodic prefixes in co-lexicographic order. We explain how our sequence differs from the previous sequence and why it had not previously been discovered.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Note: In the grandmama construction the necklaces are still the lexicographically least representatives for their rotational equivalence class, as clarified in Sect. 4.1.
References
Au, Y.H.: Shortest sequences containing primitive words and powers. Discrete Math. 338(12), 2320–2331 (2015)
Compeau, P.E.C., Pevzner, P.A., Tesler, G.: How to apply de Bruijn graphs to genome assembly. Nat. Biotechnol. 29, 987–991 (2011)
Cooper, J., Heitsch, C.: The discrepancy of the lex-least de Bruijn sequence. Discrete Math. 310, 1152–1159 (2014)
Ford, L.R.: A cyclic arrangement of \(m\)-tuples. Report No. P-1071, RAND Corp., Santa Monica (1957)
Fredricksen, H., Kessler, I.J.: An algorithm for generating necklaces of beads in two colors. Discrete Math. 61, 181–188 (1986)
Fredricksen, H., Maiorana, J.: Necklaces of beads in \(k\) colors and \(k\)-ary de Bruijn sequences. Discrete Math. 23, 207–210 (1978)
Graham, R.L., Knuth, D.E., Patashnik, O., Mathematics, C.: A Foundation for Computer Science, 2nd edn. Addison-Wesley Professional, Reading (1994)
Knuth, D.E.: The Art of Computer Programming. Combinatorial Algorithms, vol. 4A. Addison-Wesley Professional, Boston (2011)
Martin, M.H.: A problem in arrangements. Bull. Am. Math. Soc. 40, 859–864 (1934)
Moreno, E.: On the theorem of Fredricksen and Maiorana about de Bruijn sequences. Adv. Appl. Math. 33, 413–415 (2004)
Moreno, E.: On the theorem of Fredricksen and Maiorana about de Bruijn sequences. Adv. Appl. Math. 33(2), 413–415 (2004)
Moreno, E., Perrin, D.: Corrigendum to “On the theorem of Fredricksen and Maiorana about de Bruijn sequences”. Adv. Appl. Math. 62, 184–187 (2015)
Ruskey, F., Savage, C.D., Wang, T.M.Y.: Generating necklaces. J. Algorithms 13(3), 414–430 (1992)
Ruskey, F., Sawada, J., Williams, A.: De Bruijn sequences for fixed-weight binary strings. SIAM J. Discrete Math. 26(2), 605–617 (2012)
Sawada, J., Williams, A.: A Gray code for fixed-density necklaces and Lyndon words in constant amortized time. Theoret. Comput. Sci. 502, 46–54 (2013)
Sawada, J., Williams, A., Wong, D.: The lexicographically smallest universal cycle for binary strings with minimum specified weight. J. Discrete Algorithms 28, 31–40 (2014). StringMasters 2012 & 2013 Special Issue
Sawada, J., Williams, A., Wong, D., Generalizing the classic greedy, necklace constructions for de Bruijn sequences, universal cycles. Electron. J. Comb., 23(1) (2016). Paper #1.24
Stein, S.K.: Mathematics: The Man-Made Universe, 3rd edn. W. H. Freeman and Company, San Francisco (1994)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dragon, P.B., Hernandez, O.I., Williams, A. (2016). The Grandmama de Bruijn Sequence for Binary Strings. In: Kranakis, E., Navarro, G., Chávez, E. (eds) LATIN 2016: Theoretical Informatics. LATIN 2016. Lecture Notes in Computer Science(), vol 9644. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-49529-2_26
Download citation
DOI: https://doi.org/10.1007/978-3-662-49529-2_26
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-49528-5
Online ISBN: 978-3-662-49529-2
eBook Packages: Computer ScienceComputer Science (R0)