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 条

[21]

Vajnovszki V., 1997, Journal of Information & Optimization Sciences, V18, P271

[22] A loopless Gray-code algorithm for listing k-ary trees [J].

van Baronaigien, DR .

JOURNAL OF ALGORITHMS, 2000, 35 (01) :100-107

[23] GENERATING T-ARY TREES IN A-ORDER [J].

VANBARONAIGIEN, DR ;

RUSKEY, F .

INFORMATION PROCESSING LETTERS, 1988, 27 (04) :205-213

[24] A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations [J].

Wu, RY ;

Chang, JM ;

Wang, YL .

THEORETICAL COMPUTER SCIENCE, 2006, 355 (03) :303-314

[25] Grammar-oriented enumeration of binary trees [J].

Xiang, LM ;

Tang, CJ ;

Ushijima, K .

COMPUTER JOURNAL, 1997, 40 (05) :278-291

[26] Generating regular k-ary trees efficiently [J].

Xiang, LM ;

Ushijima, K ;

Akl, SG .

COMPUTER JOURNAL, 2000, 43 (04) :290-300

[27] On generating k-ary trees in computer representation [J].

Xiang, LM ;

Ushijima, K ;

Tang, CJ .

INFORMATION PROCESSING LETTERS, 2001, 77 (5-6) :231-238

[28] Efficient loopless generation of Gray codes for k-ary trees [J].

Xiang, LM ;

Ushijima, K ;

Tang, CJ .

INFORMATION PROCESSING LETTERS, 2000, 76 (4-6) :169-174

[29] LEXICOGRAPHIC GENERATION OF ORDERED TREES [J].

ZAKS, S .

THEORETICAL COMPUTER SCIENCE, 1980, 10 (01) :63-82

← 1 2 3 →