×

A calculus for the random generation of labelled combinatorial structures. (English) Zbl 0799.68143

Summary: A systematic approach to the random generation of labelled combinatorial objects is presented. It applies to structures that are decomposable, i.e. formally specifiable by grammars involving set, sequence, and cycle constructions. A general strategy is developed for solving the random generation problem with two closely related types of methods for structures of size \(n\), the boustrophedonic algorithms exhibit a worst- case behaviour of the form \(O(n\log n)\); the sequential algorithms have worst case \(O(n^ 2)\), while offering good potential for optimizations in the average case. The complexity model is in terms of arithmetic operations and both methods appeal to precomputed numerical table of linear size that can be computed in time \(O(n^ 2)\).
A companion calculus permits systematically to compute the average case cost of the sequential generation algorithm associated to a given specification. Using optimization dictated by the cost calculus, several random generation algorithms of the sequential type are developed, most of them have expected complexity \({1\over 2} n\log n\), and are thus only slightly superlinear. The approach is exemplified by the random generation of a number of classical combinatorial structures including Cayley trees, hierarchies, the cycle decomposition of permutations, binary trees, functional graphs, surjections, and set partitions.

MSC:

68R05 Combinatorics in computer science
68Q25 Analysis of algorithms and problem complexity
05A15 Exact enumeration problems, generating functions
68Q60 Specification and verification (program logics, model checking, etc.)
68R10 Graph theory (including graph drawing) in computer science
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arney, J.; Bender, E. D., Random mappings with constraints on coalescence and number of origins, Pacific J. Math., 103, 269-294 (1982) · Zbl 0514.05033
[2] Bergeron, F.; Flajolet, P.; Salvy, B., Varieties of increasing trees, (Raoult, J.-C., Proc. CAAP 92. Proc. CAAP 92, Lecture Notes in Computer Science, Vol. 581 (1992), Springer: Springer Berlin), 24-48
[3] Comtet, L., Advanced Combinatorics (1974), Reidel: Reidel Dordrecht
[4] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to Algorithms (1990), MIT Press: MIT Press New York · Zbl 1158.68538
[5] De Bruijn, N. G., Asymptotic Methods in Analysis (1981), Dover: Dover New York · Zbl 0556.41021
[6] Devroye, L., Non-Uniform Random Variate Generation (1986), Springer: Springer Berlin · Zbl 0593.65005
[7] Flajolet, P., Elements of a general theory of combinatorial structures, (Budach, L., Proc. FCT’85. Proc. FCT’85, Lecture Notes in Computer Science, Vol. 99 (1985), Springer: Springer Berlin), 112-127
[8] Flajolet, P.; Goldwurm, M.; Steyaert, J.-M., Random generation and context-free languages, Manuscript (1990)
[9] Flajolet, P.; Odlyzko, A. M., Random mapping statistics, (Quisquater, J.-J.; Vandewalle, J., Advances in Cryptology, Proc. EUROCRYPT ’89. Advances in Cryptology, Proc. EUROCRYPT ’89, Lecture Notes in Computer Science, Vol. 434 (1990), Springer: Springer Berlin), 329-354 · Zbl 0747.05006
[10] Flajolet, P.; Odlyzko, A. M., Singularity analysis of generating functions, SIAM J. Discrete Math., 3, 2, 216-240 (1990) · Zbl 0712.05004
[11] Flajolet, P.; Salvy, B.; Zimmermann, P., Automatic average-case analysis of algorithms, Theoret. Comput. Sci., 79, 1, 37-109 (1991) · Zbl 0768.68041
[12] Flajolet, P.; Zimmermann, P.; Van Cutsem, B., A calculus for the random generation of unlabelled combinatorial structures (1994), in preparation
[13] Goulden, I. P.; Jackson, D. M., Combinatorial Enumeration (1983), Wiley: Wiley New York · Zbl 0519.05001
[14] Graham, R.; Knuth, D.; Patashnik, O., Concrete Mathematics (1989), Addison-Wesley: Addison-Wesley Reading, MA
[15] Greene, D. H., Labelled formal languages and their uses, (Ph.D. thesis (June 1983), Stanford University), available as Report No. STAN-CS-83-982
[16] Greene, D. H.; Knuth, D. E., Mathematics for the Analysis of Algorithms (1981), Birkhäuser: Birkhäuser Boston, MA · Zbl 0481.68042
[17] Hickey, T.; Cohen, J., Uniform random generation of strings in a context-free language, SIAM J. Comput., 12, 4, 645-655 (1983) · Zbl 0524.68046
[18] Joyal, A., Une théorie combinatoire des séries formelles, Adv. in Math., 42, 1, 1-82 (1981) · Zbl 0491.05007
[19] Knuth, D. E., The Art of Computer Programming, (Vol. 1: Fundamental Algorithms (1968), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0191.17903
[20] Knuth, D. E., Mathematical analysis of algorithms, (Information Processing 71 (1972), North-Holland: North-Holland Amsterdam), 19-27
[21] Knuth, D. E., The Art of Computer Programming, Vol. 3: Sorting and Searching (1973), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0302.68010
[22] Knuth, D. E.; Pittel, B. A., A recurrence related to trees, Proc. Amer. Math. Soc., 105, 2, 335-349 (1989) · Zbl 0672.41024
[23] Knuth, D. E.; Schönhage, A., The expected linearity of a simple equivalence algorithm, Theort. Comput. Sci., 6, 281-315 (1978) · Zbl 0377.68024
[24] Lapointe, F.-J.; Legendre, P., The generation of random ultrametric matrices representing dendograms, J. Classification, 8, 177-200 (1991)
[25] Lengyel, T., On a recurrence involving Stirling numbers, European J. Combin., 5, 313-321 (1984) · Zbl 0559.10009
[26] Leroux, P.; Viennot, X. G., Résolution combinatoire des systèmes d’équations differentielles, II: calcul intégral combinatoire, Ann. Sci. Math. Québec, 12, 2, 233-253 (1988) · Zbl 0694.34009
[27] Li, Z.; Reingold, E. M., Solution of a divide-and-conquer maximin recurrence, SIAM J. Comput., 18, 6, 1188-1200 (1989) · Zbl 0692.68038
[28] Meir, A.; Moon, J. W., On the altitude of nodes in random trees, Canad. J. Math., 30, 997-1015 (1978) · Zbl 0394.05015
[29] Nijenhuis, A.; Wilf, H. S., Combinatorial Algorithms (1978), Academic Press: Academic Press New York · Zbl 0298.05015
[30] Rota, G.-C., Finite Operator Calculus (1975), Academic Press: Academic Press New York
[31] Salvy, B., Asymptotique automatique et fonctions génératrices, (Ph.D. thesis (1991), Ecole Polytechnique)
[32] Sedgewick, R., Algorithms (1988), Addison-Wesley: Addison-Wesley Reading, MA
[33] Soria-Cousineau, M., Méthodes d’analyse pour les constructions combinatoires et les algorithmes (1990), Doctoratès sciences, Universitéde Paris-Sud: Doctoratès sciences, Universitéde Paris-Sud Orsay
[34] Stanley, R. P., Generating functions, (Rota, G.-C., Studies in Combinatorics. Studies in Combinatorics, M.A.A. Studies in Mathematics, Vol. 17 (1978), Mathematical Association of America), 100-141
[35] Stanley, R. P., Enumerative Combinatorics, Vol. I (1986), Wadsworth: Wadsworth Belmont, CA · Zbl 0608.05001
[36] Vitter, J. S.; Flajolet, P., Analysis of algorithms and data structures, (van Leeuwen, J., Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity (1990), Elsevier: Elsevier Amsterdam), 431-524, ch. 9 · Zbl 0900.68251
[37] Wilf, H. S., Combinatorial Algorithms: An Update, CBMS-NSF Regional Conference Series (1989), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, No. 55
[38] Wilf, H. S., Generating functionology (1990), Academic Press: Academic Press New York
[39] Zimmermann, P., Séries génératrices et analyse automatique d’algorithmes, (Ph.D. thesis (1991), Ecole Polytechnique)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.