Tesis doctoral de Xavier Molinero Albareda
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.
Datos académicos de la tesis doctoral «Ordered generation of classes of combinatorial structures«
- Título de la tesis: Ordered generation of classes of combinatorial structures
- Autor: Xavier Molinero Albareda
- Universidad: Politécnica de catalunya
- Fecha de lectura de la tesis: 10/10/2005
Dirección y tribunal
- Director de la tesis
- Conrado Martínez Parra
- Tribunal
- Presidente del tribunal: marc Noy serrano
- simone Rinaldi (vocal)
- philippe Frajolet (vocal)
- t. Thiery nicolas (vocal)