A CALCULUS FOR THE RANDOM GENERATION OF LABELED COMBINATORIAL STRUCTURES

A systematic approach to the random generation of labelled combinatori al objects is presented. It applies to structures that are decomposabl e, 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: f or structures of size n, the boustrophedonic algorithms exhibit a wors t-case behaviour of the form O(n log n); the sequential algorithms hav e worst case O(n(2)), while offering good potential for optimizations in the average case. The complexity model is in terms of arithmetic op erations and both methods appeal to precomputed numerical table of lin ear size that can be computed in time O(n(2)). A companion calculus pe rmits systematically to compute the average case cost of the sequentia l generation algorithm associated to a given specification. Using opti mizations dictated by the cost calculus, several random generation alg orithms of the sequential type are developed; most of them have expect ed complexity 1/2n log n, and are thus only slightly superlinear. The approach is exemplified by the random generation of a number of classi cal combinatorial structures including Cayley trees, hierarchies, the cycle decomposition of permutations, binary trees, functional graphs, surjections, and set partitions.