Ranking and Unranking Algorithms for k-ary Trees in Gray Code Order

Authors: Fateme Ashari-Ghomi, Najme Khorasani, Abbas Nowzari-Dalini

Abstract:

In this paper, we present two new ranking and unranking algorithms for k-ary trees represented by x-sequences in Gray code order. These algorithms are based on a gray code generation algorithm developed by Ahrabian et al.. In mentioned paper, a recursive backtracking generation algorithm for x-sequences corresponding to k-ary trees in Gray code was presented. This generation algorithm is based on Vajnovszki-s algorithm for generating binary trees in Gray code ordering. Up to our knowledge no ranking and unranking algorithms were given for x-sequences in this ordering. we present ranking and unranking algorithms with O(kn2) time complexity for x-sequences in this Gray code ordering

Keywords: k-ary Tree Generation, Ranking, Unranking, Gray Code.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1072666

References:

[1] H. Ahrabian and A. Nowzari-Dalini, On the generation of binary trees from (0-1) codes, Intern. J. Comput. Math. 69 (1998), 243-251.
[2] H. Ahrabian and A. Nowzari-Dalini, Generation of t-ary trees with Ballot sequences, Intern. J. Comput. Math. 80 (2003), 1243-1249.
[3] H. Ahrabian and A. Nowzari-Dalini, Gray code algorithm for listing k-ary trees, Studies in Information and Control 13 (2004), 243-251.
[4] H. Ahrabian and A. Nowzari-Dalini, Parallel generation of binary trees in A-order, Parallel Comput. 31 (2005), 948-955.
[5] H. Ahrabian and A. Nowzari-Dalini, Parallel Generation of t-ary trees in A-order, Comput. J. 50 (2007), 581-588.
[6] A. Ahmadi-Adl, A. Nowzari-Dalini, and H. Ahrabian, Ranking and unranking algorithms for loopless generation of t-ary trees, Logic Journal of IGPL 19 (2011), 33-43.
[7] M.C. Er, Efficient generation of k-ary trees in natural order, Comput. J. 35 (1992), 306-308.
[8] S. Heubach, N. Li, and T. Mansour, Staircase tilings and k-Catalan structures, Discrete Math. 308 (2008), 5954-5964.
[9] A. Kapralski, New methods for the generation of permutations, combinations and other combinatorial objects in parallel, J. Parallel Distrib. Comput. 17 (1993), 315-329.
[10] J. Katajainen and E. Makinen, Tree compression and optimization with application, Inter. J. Found. Comput. Sci. 1 (1990), 425-447.
[11] D.E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Addision Wesly, Reading, 1973.
[12] Z. Kokosinski, On the generation of permutations through decomposition of symmetric group into cosets, Bit 30 (1990), 583-591.
[13] Z. Kokosinski, Parallel enumeration of tary trees in ASC SIMD model, International Journal of Computer Science and Network Security 11 (2011), 38-49.
[14] J.F. Korsh, Loopless generation of k-ary tree sequences, Inform. Process. Lett. 52 (1994), 243-247.
[15] J.F. Korsh and P. LaFollette, Loopless generation of Gray codes for k-ary trees, Inform. Process. Lett. 70 (1999), 7-11.
[16] J. F. Korsh and P. LaFollette, A loopless Gray code for rooted trees, ACM Transactions on Algorithms 2 (2006), 135-152.
[17] J. Lucas, D. Roelants van Baronaigien, and F. Ruskey, On rotations and the generation of binary trees, J. of Algorithms 15 (1993), 343-366.
[18] K. Manes, A. Sapounakis, I Tasoulas, and P. Tsikouras, Recursive generation of k-ary trees, Journal of Integer Sequences 12 (2009), 1-18.
[19] O. O. Olugbenga, E. F. Adebiyi, S. Fatumo and A. Dawodu, PQ trees, consecutive ones problem and applications, International Journal of Natural and Applied Sciences 4 (2008), 262-277.
[20] J. M. Pallo, A simple algorithm for generating neuronal dendritic trees, Comput. Meth. Prog. Bio. 33 (1990), 165-169.
[21] J. M. Pallo, Rotational tree structures on binary trees and triangulations, Acta Cybernetica 17 (2006), 799-810.
[22] J. M. Pallo and R. Racca, A note on generating binary trees in A-order and B-order, Intern. J. Comput. Math. 18 (1985), 27-39.
[23] F. Ruskey, Generating t-ary trees lexicographically, SIAM J. Comput. 7 (1978), 424-439.
[24] D. Roelants Van Baronaigien, A loopless Gray code algorithm for listing k-ary trees, J. Algorithms 35 (2000), 100-107.
[25] E. Seyedi-Tabari, H. Ahrabian, and A. Nowzari-Dalini, A new algorithm for generation of different types of RNA, Intern. J. Comput. Math. 87 (2010), 1197-1207.
[26] T. Uehara and W.M. Cleemput, Optical layout of cmos functional arrays, IEEE Trans. Comput. 7 (1981), 305-312.
[27] V. Vajnovszki, Constant time algorithm for generating binary tree Gray codes, Studies in Informatics and Control 5 (1996), 15-21.
[28] V. Vajnovszki and J. M. Pallo, Ranking and unranking of k-ary trees with 4k-4 letter alphabet, Journal of Information and Optimization Science 18 (1997), 271-279.
[29] V. Vajnovszki and R. Vernay, Restricted compositions and permutations: From old to new Gray codes, Inform. Process. Lett. 111 (2011), 650-655.
[30] R. Wu, J. Chang, and Y. Wang, A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations, Theor. Comput. Sci. 335 (2006), .303-314.
[31] R. Wu, J. Chang, and C. Chang, Ranking and unranking of non-regular trees with a prescribed branching sequence, Math. Comput. Model., 53 (2011), 1331-1335.
[32] L. Xiang, K. Ushijima, and C. Tang, Efficient loopless generation of Gray codes for k-ary trees, Inform. Process. Lett. 76 (2000), 169-174.
[33] S. Zaks, Lexicographic generation of ordered trees, Theor. Comput. Sci. 10 (1980), 63-82.