ALCOMFT-TR-03-15

Philippe Duchon, Philippe Flajolet, Guy Louchard and Gilles Schaeffer
Boltzmann Sampler for the Random Generation of Combinatorial Structures
INRIA. Work packages 4 and 5. July 2003.

Abstract: This article proposes a surprisingly simple framework for the random generation of combinatorial configurations based on what we call Boltzmann models. The idea is to perform random generation of possibly complex structured objects by placing an appropriate measure spread over the whole of a combinatorial class-an object receives a probability essentially proportional to an exponential of its size. As demonstrated here, the resulting algorithms based on real-arithmetic operations often operate in linear time. They can be implemented easily, % within a computer algebra system, be analysed mathematically with great precision, and, when suitably tuned, tend to be very efficient in practice.

Postscript file: ALCOMFT-TR-03-15.ps.gz (352 kb).