Generation of k-ary Trees. Extended Abstract
ILLINOIS UNIV AT URBANA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
The problem of generating ordered trees was studied rather extensively in the recent literatures. As in all problems concerning the generation of a set of combinatorial objects, there are three major aspects of the problem. After defining a certain linear ordering over the set of combinatorial objects that we are interested in we need to 1 design an algorithm for generating the combinatorial objects one by one, 2 design an algorithm for determining the rank the relative position in the linear ordering of a given combinatorial object, and 3 design an algorithm for generating the combinatorial object when its rank is given. There, in most cases, is an additional consideration, namely, to choose a suitable way to represent the combinatorial objects. For example, trees can be represented by sequences of Os and 1s, sequences of integers, and permutations of integers. Therefore, we are actually concerned with the generation, ranking, and unranking of a chosen representation of the combinatorial objects. Furthermore, a chosen representation might possess a natural linear ordering for example, the lexicographical ordering of sequences of integers which might or might not be consistent with the linear ordering over the combinatorial objects that was defined earlier. In this paper, we study ranking and unranking algorithms for k- ary trees when they are represented by sequences of Os and 1s and sequences of integers from 1 to n where n is the number of internal nodes of a tree.
- Theoretical Mathematics