# Generate a random tree population

Given

• a unbalanced k-ary tree base (with internal nodes that represent operators and leafs representing values) from the space of all unbalanced k-ary trees T
• a distance function delta(t, t') = number of edit operations to transform t into t'
• the edit operations add(t) (adding a random leaf), remove(t) (removing a random subtree), relabel(t) (relabel a random node) merge(t, t') (merge t and t')
For a genetic algorithm I need to generate a population of n trees that are not more than k edit operations away from base. I must prove that any tree within this space has equal propablity to be generated and that any tree can be generated.

The only idea I can think of was:

1. draw a random number l within [0, k]

2. define a random sequence seq of size l edit operations

3. apply seq to base

This aproach though does not garanty that any tree less than k away from base is generated?!

//EDIT

My other approach:

1. Generate a random tree rt

2. Measure distance d and calculate seq the optimal set of edit operations beween rt and base

3. apply [k-d, d] edit operations to rt

I am not shure if in that way any tree can be generated with the same propability.

• Welcome to CS.SE! It suffices to ask how to generate a single tree with the right distribution. If you can do that, you can repeat the procedure $n$ times. However, sampling with exactly that distribution looks like it might be challenging. Your methods don't yield a uniform distribution on trees. I imagine you could read about MCMC methods, but I don't know if they'll be applicable here. Would you be OK with a sampler that has approximately the right distribution, even if it's not exactly right? (Still seems like a hard problem.) – D.W. Aug 3 '18 at 19:07