A Calculus for the Random Generation of Labelled Combinatorial Structures

Philippe Flajolet 1 Paul Zimmermann 2 Bernard Van Cutsem
1 ALGO - Algorithms
Inria Paris-Rocquencourt
2 EURECA - Proof, Symbolic Computation and Logic
CRIN - Centre de Recherche en Informatique de Nancy, UHP - Université Henri Poincaré - Nancy 1
Abstract : 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(n2), 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(n2). A companion calculus permits systematically to compute the average case cost of the sequential generation algorithm associated to a given specification. Using optimizations dictated by the cost calculus, several random generation algorithms of the sequential type are developed; most of them have expected complexity View the MathML sourcen 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.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 1994, 132 (1-2), pp.1-35. 〈10.1016/0304-3975(94)90226-7〉
Liste complète des métadonnées

Contributeur : Paul Zimmermann <>
Soumis le : jeudi 12 décembre 2013 - 12:42:21
Dernière modification le : mardi 17 avril 2018 - 11:48:04

Lien texte intégral




Philippe Flajolet, Paul Zimmermann, Bernard Van Cutsem. A Calculus for the Random Generation of Labelled Combinatorial Structures. Theoretical Computer Science, Elsevier, 1994, 132 (1-2), pp.1-35. 〈10.1016/0304-3975(94)90226-7〉. 〈hal-00917729〉



Consultations de la notice