Controlled non-uniform random generation of decomposable structures
Consider a class of decomposable combinatorial structures, using different types of atoms Z = {Z(1), . . . , Z(vertical bar Z vertical bar)}. We address the random generation of such structures with respect to a size n and a targeted distribution in k of its distinguished atoms. We consider two variations on this problem. In the first alternative, the targeted distribution is given by k real numbers mu(1), . . . , mu(k) such that 0  = 0 is the number of undistinguished atoms. The structures must be generated uniformly among the set of structures of size n that contain exactly n(i) atoms Z(i) (1 <= i <= k). We give a O(r(2) Pi(k)(i=1) n(i)(2) + mnk log n) algorithm for generating m structures, which simplifies into a O(r Pi(k)(i=1) n(i) + mn) for regular specifications. (C) 2010 Elsevier B.V. All rights reserved.
random generation decomposable structures combinatorics combinatorial specification non-uniform distribution