Boltzmann Samplers for the Random Generation of Combinatorial Structures

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, be analysed mathematically with great precision, and, when suitably tuned, tend to be very efficient in practice.