Generation of K-ARY Trees,
Abstract
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 listing 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 (iii) design an algorithm for generation a combinatorial object when its rank is given. In most cases, there is an additional consideration, namely, to choose a suitable way to represent the combinatorial objects. (For example, the subsets of a set can be represented by subsets of integers corresponding to the elements in the set, or by 0-1 vectors, and so on). Therefore, we are actually concerned with the listing, 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 listing, ranking, and unranking algorithms for K-ary trees when they are represented by permutations of multi-sets, by sequences of 0's and 1's, and by sequences of integers.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1980
- Accession Number
- ADA102229
Entities
People
- Chung Laung Liu
Organizations
- University of Illinois Urbana–Champaign