A Calculus of Random Generation

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 union, product, 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 TeX ; the sequential algorithms have worst case TeX , while offering good potential for optimizations in the average case. (Both methods appeal to precomputed numerical tables of linear size). A companion calculus permits to systematically 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 are developed, based on the sequential principle; most of them have expected complexity 1/2 n log n, thus being 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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-00917730
Contributor : Paul Zimmermann <>
Submitted on : Thursday, December 12, 2013 - 12:42:22 PM
Last modification on : Monday, January 28, 2019 - 6:34:02 PM

Links full text

Identifiers

Collections

Citation

Philippe Flajolet, Paul Zimmermann, Bernard Van Cutsem. A Calculus of Random Generation. Proceedings of the First European Symposium on Algorithms (ESA'93), 1993, Bad Honnef, Germany. pp.169-180, ⟨10.1007/3-540-57273-2_53⟩. ⟨hal-00917730⟩

Share

Metrics

Record views

277