ALCOMFT-TR-01-189

Philippe Duchon, Philippe Flajolet, Guy Louchard and Gilles Schaeffer
Random Sampling from Boltzmann Principles
INRIA. Work package 5. December 2001.

Abstract: This note proposes a new framework for 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. The resulting algorithms 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-01-189.ps.gz (112 kb).