Random Generation of Combinatorial Structures using Context-Fee Grammars

The problem of computing a random combinatorial structure such as balanced strings, trees, and flowcharts arises in a variety of applications, including the evaluation of heuristic algorithms which use these structures. The main challenge here is to assure that each instance of the possible structure has the same probability of selection. A brute-force method of first creating a list of all instances of the structure with a given size, say, and then choosing one from the list at random is typically impractical because of the very large number of instances. We provide here a unified approach, using context-free grammars as a backbone for defining the desired combinatorial structure, for efficiently generating a random instance of that structure. The algorithm typically takes a linear or quadractic amount of time in the size of the structure, following some initial computations which is also polynomial in the size of the structure.