A generic approach for the unranking of labeled combinatorial classes

in this article, we design and analyze algorithms that solve the unranking problem (i.e.. generating a combinatorial structure of size, n given its ra nk) for a large collection of labeled combinatorial classes. those that can be built using operators like unions (+), products (*), sequences, sets. c ycles, and substitutions. We also analyze the performance of these algorith ms and show that the worst-case is o(n(2)) (o(nlogn) if the so-called boust rophedonic order is used), and provide an algebra for the analysis of the a verage performance and higher-order moments together with a few examples of its application. (C) 2001 John Wiley & Sons, Inc.