Necklaces and Lyndon words in colexicographic and binary reflected Gray code order

Journal of Discrete Algorithms - Tập 46 - Trang 25-35 - 2017
Joe Sawada, Aaron Williams, Dennis Wong

Tài liệu tham khảo

Booth, 1980, Lexicographically least circular substrings, Inf. Process. Lett., 10, 240, 10.1016/0020-0190(80)90149-0 Cattell, 2000, Fast algorithms to generate necklaces, unlabeled necklaces, and irreducible polynomials over GF(2), J. Algorithms, 37, 267, 10.1006/jagm.2000.1108 Degni, 2007, Gray-ordered binary necklaces, Electron. J. Comb., 14 Dragon, 2016, The grandmama de Bruijn sequence for binary strings, 347 Fredricksen, 1986, An algorithm for generating necklaces of beads in two colors, Discrete Math., 61, 181, 10.1016/0012-365X(86)90089-0 Fredricksen, 1978, Necklaces of beads in k colors and k-ary de Bruijn sequences, Discrete Math., 23, 207, 10.1016/0012-365X(78)90002-X F. Gray, Pulse code communication. U.S. Patent 2,632,058, 1953. Ruskey, 1996 Ruskey, 1992, Generating necklaces, J. Algorithms, 13, 414, 10.1016/0196-6774(92)90047-G Ruskey, 1999, An efficient algorithm for generating necklaces with fixed density, SIAM J. Comput., 29, 671, 10.1137/S0097539798344112 A. Sabri, V. Vajnovszki, Two Reflected Gray Code based orders on some restricted growth sequences, ArXiv e-prints, June 2013. Sawada, 2013, A Gray code for fixed-density necklaces and Lyndon words in constant amortized time, Theor. Comput. Sci., 502, 46, 10.1016/j.tcs.2012.01.013 Vajnovszki, 2007, Gray code order for Lyndon words, Discrete Math. Theor. Comput. Sci., 9, 145 Vajnovszki, 2008, More restrictive Gray codes for necklaces and Lyndon words, Inf. Process. Lett., 106, 96, 10.1016/j.ipl.2007.10.011 Wang, 1997, A Gray code for necklaces of fixed density, SIAM J. Discrete Math., 9, 654, 10.1137/S089548019528143X Weston, 2006, Gray codes for necklaces and Lyndon words of arbitrary base, Pure Math. Appl. (PU.M.A.), 17, 175