Ranking and unranking algorithms for loopless generation of t-ary trees

被引：10

作者：

Ahmadi-Adl, Amin ^{[1
]}

Nowzari-Dalini, Abbas ^{[1
]}

Ahrabian, Hayedeh ^{[1
]}

机构：

[1] Univ Tehran, Ctr Excellence Bioinformat, Sch Math Stat & Comp Sci, Tehran, Iran

来源：

LOGIC JOURNAL OF THE IGPL | 2011年 / 19卷 / 01期

关键词：

Generation algorithm; Gray-code; ranking and unranking algorithms; PARALLEL GENERATION; BINARY-TREES; GRAY CODES;

D O I：

10.1093/jigpal/jzp097

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, we present two new ranking and unranking algorithms for z-sequences in Gray-code order. These algorithms are designed based on a loopless generation algorithm which is given for z-sequences corresponding to t-ary trees by Roelants van Baronaigien and Xiang et al. Up to our knowledge no other ranking and unranking algorithms are given for Gray-codes corresponding to t-ary trees. The time complexity of both algorithms for t-ary trees with n nodes is O(n(2)t).

引用

页码：33 / 43

页数：11

共 29 条

[1] Parallel generation of binary trees in A-order [J].

Ahrabian, H ;

Nowzari-Dalini, A .

PARALLEL COMPUTING, 2005, 31 (8-9) :948-955

[2] Generation of t-ary trees with Ballot-sequences [J].

Ahrabian, H ;

Nowzari-Dalini, A .

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2003, 80 (10) :1243-1249

[3]

Ahrabian H., 2004, Studies in Informatics and Control, V13, P243

[4]

Ahrabian H., 1987, COMPUT J, V30, P569

[5] Parallel generation of t-ary trees in A-order [J].

Ahrabiani, H. ;

Nowzari-Dalini, A. .

COMPUTER JOURNAL, 2007, 50 (05) :581-588

[6] EFFICIENT GENERATION OF K-ARY TREES IN NATURAL ORDER [J].

ER, MC .

COMPUTER JOURNAL, 1992, 35 (03) :306-308

[7] Staircase tilings and k-Catalan structures [J].

Heubach, Silvia ;

Li, Nelson Y. ;

Mansour, Toufik .

DISCRETE MATHEMATICS, 2008, 308 (24) :5954-5964

[8] NUMBERING SYSTEM FOR BINARY TREES [J].

KNOTT, GD .

COMMUNICATIONS OF THE ACM, 1977, 20 (02) :113-115

[9]

Knuth D. E., 1973, The Art of Computer Programming A Combinatorial algorithms, V1

[10]

Korsh J. F., 1995, Journal of Information & Optimization Sciences, V16, P557

← 1 2 3 →