Loopless Algorithms for Listing Zaks' Sequences in Gray-Code Order

Abstract

A k-ary tree is a rooted and ordered tree such that every internal node has exactly k children. A natural representation of k-ary trees is the use of z-sequences (or x-sequences) introduced by Zaks in 1980. Under such representation, loopless algorithms for generating z-sequences of k-ary trees in Gray-code order were developed by van Baronaigien (2000) and Xiang et al. (2000), respectively. In this paper, we present a new loopless algorithm to generate z-sequences of k-ary trees in Gray-code order. The development requires almost half of memory space and is shown to be more efficient than the existing algorithms by experimental results. In particular, constant upper bounds for the expected numbers of operations (e.g., assignments and comparisons) are derived. Moreover, with a slight modification, our algorithm can generate x-sequences of k-ary trees so that each successive sequence is obtained from its predecessor by changing one ＂0＂ to a ＂1＂ and one ＂1＂ to a ＂0.＂