Boltzmann sampling and random generation of combinatorial structures

Boltzmann models, inspired from statistical physics, amount to assigning to each object in a combinatorial class a probability proportional to an exponential of its size. We show here that such models can be used to derive efficient random generators (or samplers), which can be built systematically from formal specifications. The algorithms apply in both the labelled and unlabelled universe and they can be tuned to target a certain size range. As a consequence, one can often obtain approximate-size samplers of linear complexity and exact size samplers of subquadratic complexity. Various applications to words, trees, permutations, graphs, mappings, allocations, partitions, and maps will be outlined. Structures with sizes in the range between 10,000 and a million can be routinely generated in this way. (Based on joint works with Philippe Duchon, Éric Fusy, Guy Louchard, Carine Pivoteau, and Gilles Schaeffer).