Accession Number:

ADA102229

Title:

Generation of K-ARY Trees,

Descriptive Note:

Corporate Author:

ILLINOIS UNIV AT URBANA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1980-01-01

Pagination or Media Count:

26.0

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 0s and 1s, and by sequences of integers.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE