On the uniformly random generation of combinatorial structures

Abstract

We consider two algorithmic processes used to sample uniformly from a wide array of combinatorial classes. First, the recursive method which uses the recur- sive decomposition of a class in addition to tables of large integers which count the objects of a given size to generate objects uniformly at random. Second, the more recent Boltzmann model for sampling is considered. Boltzmann models rely on the use of the closed form generating function of a class and address the space constraints imposed by the recursive method with a time efficiency trade off. Implementations for three classes of objects (binary trees, integer partitions, and set partitions) are demonstrated for each method. Comparison and analysis of the two methods are discussed in addition to applications.