A generic approach for the unranking of labeled combinatorial classes

Conrado Martı́nez, Xavier Molinero

Random Structures and Algorithms · 2001 · 24 citations · 12 references

Concepts

Abstract

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

References

12