Random Structures and Algorithms · 2001 · 24 citations · 12 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsSet TheoryCombinatorial EnumerationCombinatorial OptimizationEnumerative CombinatoricsRanking ProblemsCombinatorial RepresentationsEnumeration Of Combinatorial ClassesMoments
Abstract In this article, we design and analyze algorithms that solve the unranking problem (i.e., generating a combinatorial structure of size, n given its rank) for a large collection of labeled combinatorial classes, those that can be built using operators like unions (+), products (⋆), sequences, sets, cycles, and substitutions. We also analyze the performance of these algorithms and show that the worst‐case is 𝒪( n 2 ) (𝒪( n log n ) if the so‐called boustrophedonic order is used), and provide an algebra for the analysis of the average performance and higher‐order moments together with a few examples of its application. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 472–497, 2001
12
On the Altitude of Nodes in Random Trees
A. Meir, J. W. Moon · Canadian Journal of Mathematics · 1978 · 367 citations · Full text
On Rotations and the Generation of Binary Trees
Joan M. Lucas, D.R. Vanbaronaigien, Frank Ruskey · Journal of Algorithms · 1993 · 105 citations