Resumen de Ordered generation of classes of combinatorial structures
There are four distinct but closely related problems about the generation of combinatorial objects: drawing (generate a random object of a given combinatorial class and size), ranking (compute the rank of a given object from a combinatorial class, according to some previously fixed order), unranking (generate a combinatorial object whose rank and size are given, according to a fixed specific order) and iteration or exhaustive generation (generate all objects of a given combinatorial class and size, according to some fixed order), In this thesis we combine some well-known principles and novel ideas in a generic framework to design efficient solutions to the last three problems. Our algorithms are generic in the sense that their input considers a finite specification of the combinatorial class whose objects we deal with.
We provide algorithms for unranking and ranking objects of size n with average cost O(n sqrt n) for the lexicographic order and O(n log n) for the boustrophedonic order. In the case of iterative classes (classes where recursion is not used to specify them), the cost is Theta(n). Furthermore, we have also studied several heuristics to improve the performance of the unranking algorithms, and the probability distribution of the cost of unranking labelled classes with lexicographic ordering.
For the iteration problem, we have designed algorithms with constant amortized cost for a large family of admissible classes, including the most interesting classes (we call them superexpoentiallabelled admissible classes, and superpolynomial unlabelled admissible classes). We have also introduced several techniques (e.g., the use of finger pointers) to improve the performance.
The flexibility of our generic algorithms makes them attractive for rapid prototyping and for their inclusion in general combinatorial libraries, like the COMBSTRUCT package for MAPLE or the MUPAD-CombINAT package for MUPAD.
