Abstract
Several techniques are given for the uniform generation of trees for use in Monte Carlo studies of clustering and tree representations. First, general strategies are reviewed for random selection from a set of combinatorial objects with special emphasis on two that use random mapping operations. Theorems are given on how the number of such objects in the set (e.g., whether the number is prime) affects which strategies can be used. Based on these results, methods are presented for the random generation of six types of binary unordered trees. Three types of labeling and both rooted and unrooted forms are considered. Presentation of each method includes the theory of the method, the generation algorithm, an analysis of its computational complexity and comments on the distribution of trees over which it samples. Formal proofs and detailed algorithms are in appendices.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
BEYER, T., and HEDETNIEMI, S. M. (1980), “Constant Time Generation of Rooted Trees,”SIAM Journal of Computing, 9, 706–712.
CARROLL, J. D., and CHANG, J.-J. (1973), “A Method for Fitting a Class of Hierarchical Tree Structure Models to Dissimilarities Data and Its Application to Some ‘Body Parts’ Data of Miller's,”Proceedings of the 81st annual convention of the American Psychological Association, 8, 1097–1098.
CARROLL, J. D., and CHANG, J.-J. (1974), “A General Procedure for Fitting Tree Structure Models to Dissimilarity Data,” Unpublished Bell Laboratories Technical Memorandum. Presented at the annual meeting of the Classification Society, North American Branch.
COMTET, L. (1970),Advanced Combinatorics, Boston: D. Reidel Publishing Co.
DESOETE, G., DESARBO, W., FURNAS, G. W., and CARROLL, J. D. (1984), “The Representation of Nonsymmetric Rectangular Proximity Data by Ultrametric and Path Length Tree Structures,”Psychometrika, 49, 289–310.
DINITS, E. A., and ZAITSEV, M. A. (1977), “Algorithm for the Generation of Nonisomorphic Trees,”Avtom. and Telemekh. (USSR)38 121–126, Trans in:Automation and Remote Control (USA), 4, 554–558.
FELSENSTEIN, J. (1978), “The Number of Evolutionary Trees,”Systematic Zoology, 27, 27–33.
FOWLKES, E. B., MALLOWS, C. L., and MCRAE, J. E. (1982), “Some methods for Studying the Shape of Hierarchical Trees,” Unpublished Bell Laboratories Technical Memorandum.
FRANK, O., and SVENSSON, K. (1981), “On Probability Distributions of Single-Linkage Dendrograms,”Journal of Statistical Computation and Simulation, 12, 121–131.
FURNAS, G. W. (1981), “The Construction of Random Terminally Labeled, Binary Trees,” Unpublished Bell Laboratories Technical Memorandum.
GOBEL, F. (1981), “On a 1-1-Correspondence between Rooted Trees and Natural Numbers,”Journal of Combinatorial Theory Series B,29, 141–143.
HARARY, F. (1969),Graph Theory, Reading, Mass: Addison-Wesley, Chapter 4.
HARDING, E. F. (1971), “The Probabilities of Rooted Tree-Shapes Generated by Random Bifurcation,”Advances in Applied Probability, 3, 44–77.
KNOTT, G. D. (1977), “A Numbering System for Binary Trees,”Communication of the Association for Computing machinery, 20(2).
KNUTH, D. E., (1973),The Art of Computer Programming, second edition. Volume I. Reading, Mass: Addison-Wesley.
KOZINA, A. V. (1979), “Coding and Generation of Nonisomorphic Trees,”Kibernetika (USSR) 15, 38–43, Trans. in:Cybernetics (USA) 15, 645–651.
LAPTIN, Y. P. (1981), “An External Problem on Random Trees,” Plenum Publishing Corporation. Translated fromKibernetika, 2, 95–97.
MEIR, A., and MOON, J. W. (1970), “The Distance between Points in Random Trees,”Journal of Combinatorial Theory, 8, 99–103.
MURTAGH, F. (1983), “A Probability Theory of Hierarchic Clustering using Random Dendrograms,”Journal of Statistical Computation and Simulation, 18, 145–157.
MURTAGH, F. (1984), “Counting Dendrograms: A Survey,”Discrete Applied Mathematics, 7, 191–199.
NIJENHUIS, A., and WILF, H. S. (Eds.) (1978),Combinatorial Algorithms for Computers and Calculators, Second Edition, New York: Academic Press.
ODEN, N. L. and SHAO, K-T (1984), “An Algorithm to Equiprobably Generate all Directed Trees with K Labeled Terminal Nodes and Unlabeled Interior Nodes,”Bulletin of Mathematical Biology, in press.
PROSKUROWSKI, A. (1980), “On the Generation of Binary Trees,”Journal of the Association for Computing Machinery, 27, 1–2.
PRUZANSKY, S., TVERSKY, A., and CARROLL, J. D. (1982), “Spatial vs. Tree Representations of Proximity Data,”Psychometrika, 47, 3–24.
READ, R. C. (1972), “The Coding of Various Kinds of Unlabeled Trees,” InGraph Theory and Computing, ed. R. C. Read, New York: Academic Press, 153–182.
READ, R. C. (1978), “Every one a Winner or How to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations,”Annals of Discrete Mathematics, 2, 107–120.
ROBINSON, R. W., and SCHWENK, A. J. (1975), “The Distribution of Degrees in a Large Random Tree,”Discrete Mathematics, 12, 359–372.
ROHLF, F. J. (1983), “Numbering Binary Trees with Labeled Terminal Vertices,”Bulletin of Mathematical Biology, 45, 33–40.
ROTEM, D., and VAROL, Y. L. (1978), “Generation of Binary Trees from Ballot Sequences,”Journal of the Association for Computing Machinery, 25, 396–404.
RUSKEY, F. (1978), “Generating t-ary Trees Lexicographically,”SIAM Journal of Computing, 7(4, 424–439.
RUSKEY, F., and HU, T. C. (1977), “Generating Binary Trees Lexicographically,”SIAM Journal of Computing, 6, 748–758.
SATTATH, S., and TVERSKY, A. (1977), “Additive Similarity Trees,”Psychometrika, 42, 319–345.
SIBSON, R. (1972), “Order Invariant Methods for Data Analysis,”Journal of the Royal Statistical Society, B34, 311–349.
SOLOMON, M., and FINKEL, R. A. (1980), “A Note on Enumerating Binary Trees,”Journal of the Association for Computing Machinery, 27, 3–5.
TROJANOWSKI, A. E. (1978), “Ranking and Listing Algorithms for k-ary Trees,”SIAM Journal of Computing, 7, 492–509.
WILF, H. S. (1981), “The Uniform Selection of Free Trees,”Journal of Algorithms, 2, 204–207.
ZAKS, S. (1982), “Generation and Ranking of k-ary Trees,”Information Processing Letters (Netherlands),14, 44–48.
ZAKS, S., and RICHARDS, D. (1979), “Generating Trees and other Combinatorial Objects Lexicographically,”SIAM Journal of Computing, 8, 73–81.
Author information
Authors and Affiliations
Additional information
This work was supported by the Alfred P. Sloan Foundation through the Center for Cognitive Science of The University of Texas at Austin, by Bell Communications Research, Inc., and by the Bell Laboratories. The author would like to thank W. H. E. Day for his extensive comments on an early draft of this manuscript, and K. E. Lochbaum for her help in programming and proofreading.
Rights and permissions
About this article
Cite this article
Furnas, G.W. The generation of random, binary unordered trees. Journal of Classification 1, 187–233 (1984). https://doi.org/10.1007/BF01890123
Issue Date:
DOI: https://doi.org/10.1007/BF01890123