|
Abstract : |
Gaia is a computer algebra package that helps counting and drawing random combinatorial structures of various sorts. It is an implementation of the calculus developed by Ph. Flajolet, B. Van Cutsem and the author in [5]. Given a combinatorial specification and an integer n, it draws a random object uniformly amongst all size n structures. It applies to all decomposable structures, either labelled or unlabelled, including trees of various kinds, surjections, set partitions, permutations, functional graphs of many sorts. Some applications of random generation are: (i) analyzing the average case complexity of algorithms by making simulations to guess or to check analytic results, (ii) checking the correctness of programs by feeding them with random inputs, (iii) getting ideas about some parameter of a class of objects, for example the height of trees or the number of connected components of graphs, (iv) simply drawing a random object. Uniform random generation is difficult because there is generally no closed formula for the number A n of data structures of size n, and secondly most methods require an explicit bijection with integers modulo A n, but such a bijection is known only in a few cases (for example permutations and integer partitions, see the combinat package). The main idea underlying the Gaia system is first to transform the specification of a combinatorial class into a standard specification restricted to atoms and union, product, pointing constructors; then the standard specification is translated into counting and drawing procedures using some well-defined templates. This ensures a really uniform random generation in O(n log n) arithmetic operations in the worst case, after a O(n, |
