Abstract
We describe in this extended abstract the experiments that we have conducted in order to fullfil the following goals: a) to obtain a working implementation of the unranking algorithms that we have presented in previous works; b) to assess the validity and range of application of our theoretical analysis of the performance of these algorithms; c) to provide preliminary figures on the practical performance of these algorithms under a reasonable environment; and finally, d) to compare these algorithms with the algorithms for random generation. Additionally, the experiments support our conjecture that the average complexity of boustrophedonic unranking is Θ(nlog n) for many combinatorial classes (namely, those whose specification requires recursion) and that it performs only slightly worse than lexicographic unranking for iterative classes (those which do not require recursion to be specified).
This research was supported by the Future and Emergent Technologies programme of the EU under contract IST-1999-14186 (ALCOM-FT) and the Spanish “Ministerio de Ciencia y Tecnología” programme TIC2002-00190 (AEDRI II).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Nievergelt, J., Reingold, E.M., Deo, N.: Combinatorial Algorithms: Theory and Practice. Prentice-Hall, Englewood Cliffs (1977)
Even, S.: Combinatorial Algorithms. MacMillan, New York (1973)
Flajolet, P., Salvy, B.: Computer algebra libraries for combinatorial structures. J. Symbolic Comp (also INRIA, num. 2497) 20, 653–671 (1995)
Flajolet, P., Sedgewick, R.: The average case analysis of algorithms: Counting and generating functions. Technical Report 1888, INRIA (April 1993)
Flajolet, P., Vitter, J.S.: Average-case Analysis of Algorithms and Data Structures. In: Van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, ch. 9, North-Holland, Amsterdam (1990)
Flajolet, P., Zimmermann, P., Van Cutsem, B.: A calculus for the random generation of combinatorial structures. Theor. Comp. Sci. 132(1), 1–35 (1994)
Kreher, D.L., Stinson, D.R.: Combinatorial Algorithms: Generation, Enumeration and Search. CRC Press LLC, Boca Raton (1999)
Liebehenschel, J.: Ranking and unranking of lexicographically ordered words: An average-case analysis. Journal of Automata, Languages and Combinatorics 2(4), 227–268 (1997)
Liebehenschel, J.: Ranking and unranking of a generalized dyck language and the application to the generation of random trees. In: The Fifth International Seminar on the Mathematical Analysis of Algorithms, Bellaterra, Spain (June 1999)
Martínez, C., Molinero, X.: Unranking of labelled combinatorial structures. In: Krob, D., Mikhalev, A.A., Mikhalev, A.V. (eds.) Formal Power Series and Algebraic Combinatorics: 12th International Conference; Procedings / FPSAC 2000, June 2000, pp. 288–299. Springer, Heidelberg (2000)
Martínez, C., Molinero, X.: A generic approach for the unranking of labeled combinatorial classes. Random Structures & Algorithms 19(3-4), 472–497 (2001)
Martínez, C., Molinero, X.: Generic algorithms for the generation of combinatorial objects. In: Rovan, B., Vojtáš, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 572–581. Springer, Heidelberg (2003)
Nijenhuis, A., Wilf, H.S.: Combinatorial Algorithms: For Computers and Calculators. Academic Press, Inc., London (1978)
Pallo, J.M.: Enumerating, ranking and unranking binary trees. The Computer Journal 29(2), 171–175 (1986)
Wilf, H.S.: East side, west side.. an introduction to combinatorial families-with maple programming (February 1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Martínez, C., Molinero, X. (2004). An Experimental Study of Unranking Algorithms. In: Ribeiro, C.C., Martins, S.L. (eds) Experimental and Efficient Algorithms. WEA 2004. Lecture Notes in Computer Science, vol 3059. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24838-5_25
Download citation
DOI: https://doi.org/10.1007/978-3-540-24838-5_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22067-1
Online ISBN: 978-3-540-24838-5
eBook Packages: Springer Book Archive