Accesso libero

On the exhaustive generation of generalized ballot sequences in lexicographic and Gray code order

INFORMAZIONI SU QUESTO ARTICOLO

Cita

[1] A. Bernini, S. Bilotta, R. Pinzani, A. Sabri and V. Vajnovszki, Reected Gray codes for q-ary words avoiding a given factor, Acta Inform., 52 (2015) 573–592.10.1007/s00236-015-0225-2Search in Google Scholar

[2] J. Bertrand, Solution d'un probléme, C. R. Math. Acad. Sci. Paris, 105 (1887) 369.Search in Google Scholar

[3] M. C. Er, On generating the N-ary reected Gray code, IEEE Trans. Comput., 33 (1984) 739-741.10.1109/TC.1984.5009360Search in Google Scholar

[4] F. Gray, Pulse code communication, U.S. Patent 2632058, 1953.Search in Google Scholar

[5] P. Klingsberg, A Gray code for compositions, J. Algorithms, 3 (1981) 41–44.10.1016/0196-6774(82)90006-2Search in Google Scholar

[6] D. E. Knuth, Dancing links, available at https://arxiv.org/pdf/cs/0011047.pdf.Search in Google Scholar

[7] J. M. Lucas, D. R. van Baronaigien and F. Ruskey, On rotations and the generation of binary trees, J. Algorithms, 15 (1993) 1-24.10.1006/jagm.1993.1045Search in Google Scholar

[8] N. J. A. Sloane, The On-line Encyclopedia of Integer Sequences, at http://oeis.org.Search in Google Scholar

[9] M. Renault, Lost (and found) in translation: André's actual method and its application to the generalized ballot problem, Amer. Math. Monthly, 115 (2008) 358–363.10.1080/00029890.2008.11920537Search in Google Scholar

[10] F. Ruskey, Combinatorial Generation, in preparation, 2003.Search in Google Scholar

[11] A. Sabri and V. Vajnovszki, Two reected Gray code based orders on some restricted growth sequences, The Computer Journal, 58 (2015) 1099–1111.10.1093/comjnl/bxu018Search in Google Scholar

[12] A. Sabri and V. Vajnovszki, More restricted growth functions: Gray codes and exhaustive generations, Graphs Combin., 33 (2017) 573–582.10.1007/s00373-017-1774-7Search in Google Scholar

[13] A. Sabri, V. Vajnovszki, Exhaustive generation for ballot sequences in lexicographic and Gray code order, In: L. Ferrari, M. Vamvakari (Eds.), Proceedings of the 11th International Conference on Random and Exhaustive Generation of Combinatorial Structures, Athens, Greece, June 18-20, 2018. CEUR Workshop Proceedings, 2113 (2018) 195–201.Search in Google Scholar

[14] B. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, Springer-Verlag, New York, 2001.10.1007/978-1-4757-6804-6_3Search in Google Scholar

[15] R. P. Stanley, Enumerative Combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, 62. Cambridge University Press, Cambridge, 1999.Search in Google Scholar

[16] V. Vajnovszki, A loopless generation of bitstrings without p consecutive ones, In: C. S. Calude, M. J. Dineen, S. Sburlan (Eds.), Combinatorics, Computability and Logic. Discrete Mathematics and Theoretical Computer Science. Springer-Verlag, London, 2001, pp. 227–240.10.1007/978-1-4471-0717-0_19Search in Google Scholar

[17] V. Vajnovszki, More restrictive Gray codes for necklaces and Lyndon words, Inform. Process. Lett., 106 (2008) 96–99.10.1016/j.ipl.2007.10.011Search in Google Scholar

[18] V. Vajnovszki and R. Vernay, Restricted compositions and permutations: from old to new Gray codes, Inform. Process. Lett., 111 (2011) 650–655.10.1016/j.ipl.2011.03.022Search in Google Scholar

[19] T. Walsh, Loop-free sequencing of bounded integer compositions, J. Combin. Math. Combin. Comput., 33 (2000) 323–345.Search in Google Scholar

[20] T. Walsh, Generating Gray codes in O(1) worst-case time per word, Lecture Notes in Comput. Sci., 2731 (2003) 71–88.10.1007/3-540-45066-1_5Search in Google Scholar