Efficient loopless generation of Gray codes for k-ary trees

被引：22

作者：

Xiang, LM

Ushijima, K

Tang, CJ

机构：

[1] Kyushu Univ, Dept Comp Sci & Commun Engn, Higashi Ku, Fukuoka 8128581, Japan

[2] Sichuan Univ, Dept Comp Sci, Chengdu 610064, Sichuan, Peoples R China

来源：

INFORMATION PROCESSING LETTERS | 2000年 / 76卷 / 4-6期

关键词：

combinatorial problems; Gray codes; k-ary trees; loopless generation;

D O I：

10.1016/S0020-0190(00)00139-3

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Vajnovszki recently developed a loopless algorithm [Inform. Process. Lett. 68 (1998) 113] to enumerate Gray codes for binary trees, and then Korsh and Lafollette gave a loopless algorithm [Inform. Process. Lett 70 (1999) 7] to generate Gray codes for k-ary trees. In this paper, another loopless algorithm is presented to list Gray codes for k-ary trees more efficiently in both space and time than the two former algorithms, and the algorithm is also conceptually simpler than the predecessors. Based on the algorithm, Gray codes for k-ary trees with n internal nodes (n greater than or equal to 2 and k > 3) can be generated in at least 2(2(n-1)) different ways easily. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：169 / 174

页数：6

共 15 条

[1]

Gill Williamson S., 1985, COMBINATORICS COMPUT

[2] Loopless generation of Gray codes for k-ary trees [J].