# Uniformly random iteration of subtrees

I want to iterate through the first $$k$$ elements of a randomly ordered list containing all subtrees for a given tree. The definition of subtrees that I'm using is: "A subtree of $$T$$ is a subgraph of $$T$$ that is also a tree". For example, a tree $$A(B(D, E, F), C(G, H))$$ should have 62 subtrees if my math is correct.

The amount of subtrees can be calculated as follows. Let us denote by $$R(T)$$ the number of subtrees of $$T$$ rooted at $$T$$. If $$T$$ is a leaf then $$R(T) = 1$$, and if tree has children $$T_1,\ldots,T_\ell$$ then $$R(T) = \prod_{i=1}^\ell (R(T_i) + 1).$$ Finally, the number of subtrees of $$T$$ is $$\sum_{x \in T} R(T_x)$$, where $$x$$ goes over all vertices of $$T$$, and $$T_x$$ is the subtree induced by $$x$$ (consisting of $$x$$ and all of its progeny).

By shuffling the order of these trees and listing the first 5, the result might be $$C(G), A(B(F)), B(D, E), A(B, C), C$$.

I can already generate a full list of subtrees. For larger trees, this quickly becomes impossibly large. I am looking for a way of generating these subtrees without having to generate all of them.

One possible method I've thought of is to keep a count of how many unseen rooted subtrees each of the nodes has left, and decrementing each time a subtree is generated from that node. The probability that a node is selected would be weighted by this counter. I would also have to prevent the generation of duplicates. I was wondering if there is a better way.

• Can you define a "subtree" more precisely? Normally I'd think of a subtree as being determined by a node plus all of its descendants, but it sounds like that's not what you had in mind. So what do you have in mind? An example tree with a count of the number of subtrees is not an adequate substitute for a clear definition of what you mean by "subtree" (it forces me to guess/reverse-engineer how you define subtree). Perhaps you mean that a subtree is any tree that can be obtained by repeatedly deleting a node and all of its descendants? Can you edit the question to clarify? – D.W. Feb 8 '19 at 1:11
• Do you know how to build an efficient algorithm to count the number of trees, given the tree as input? I suggest you take a minute to see if you can figure out how to do that using dynamic programming. If you can, I suggest editing the question to show your algorithm for that, as I can tell you how to use that to pick a random subtree. If you can't, I suggest editing the question to state that (and tell us about your level of understanding, so we can tailor our answer appropriately. And finally... welcome to CS.SE! – D.W. Feb 8 '19 at 1:13
• @D.W. I've edited my question, which now includes the algorithm for counting the subtrees. I think the definition for "subtree" that you mentioned was also the one I was using, hopefully it is more clear now. Thanks! – anlew Feb 8 '19 at 2:35

If $$k \leq (1-\epsilon) N$$, where $$N$$ is the total number of subtrees, then the following approach would work:

1. Start with the empty list $$L$$.

2. Repeat $$k$$ times:

• Pick a random subtree $$T'$$.
• If $$T' \notin L$$, add it to $$L$$; otherwise, go back to the previous step.

Since $$k \leq (1-\epsilon) N$$, the expected number of times it takes to find $$T' \notin L$$ is at most $$1/\epsilon$$ throughout the process; it will be much smaller in the beginning. In particular, if $$k \ll \sqrt{N}$$, then it is highly likely that you will never generate the same subtree twice.

In more detail, the average expected number of repetitions is $$\frac{1}{k} \sum_{\ell=0}^{k-1} \frac{N}{N-\ell} \approx \frac{N}{k} \int_0^k \frac{dx}{N-x} = \frac{N}{k} \ln \frac{N}{N-k} \approx \frac{N}{N-k} = 1 + \frac{k}{N-k}.$$

You can implement the check $$T' \notin L$$ quickly using a hashtable. In this way, we have reduced your problem to that of generating a uniformly random subtree, which you can do as follows, essentially by reducing the problem of uniform generation to that of counting.

In order to pick the root of the subtree, first compute $$R(T_x)$$ for every vertex $$x \in T$$ (you can do this in $$O(n)$$ for all vertices together if you're careful, where $$n$$ is the number of vertices). The root is $$x$$ with probability $$R(T_x)/N$$ (you can choose $$x$$ quickly using binary search, for example).

If $$x$$ is a leaf, then we're done. Otherwise, suppose that $$x$$ has children $$x_1,\ldots,x_\ell$$. Your random subtree skips $$x_i$$ with probability $$1/(1+R(T_{x_i}))$$ (independently). If it doesn't skip $$x_i$$, then you generate a random subtree of $$T_{x_i}$$ recursively.

Here are two other related approaches. The first is to generate all subtrees, permute them randomly in $$O(N)$$, and then output the prefix of length $$k$$.

A variant of the first approach uses unranking. By modifying the approach above, you can take an integer in the range $$0,\ldots,N-1$$ and convert it to a subtree. This goes as follows. Let $$x_1,\ldots,x_n$$ be an enumeration of the vertices of $$T$$. The first $$R(T_{x_1})$$ integers correspond to subtrees rooted at $$x_1$$. The following $$R(T_{x_2})$$ integers correspond to subtrees rooted at $$x_2$$. And so on.

Now suppose we're given an integer $$i$$ in the range $$0,\ldots,R(T_x)-1$$, and need to convert it to a subtree rooted at $$x$$. If $$x$$ is a leaf, then there is nothing to do. Otherwise, let $$x_1,\ldots,x_\ell$$ be the children of $$x$$. We first convert $$i$$ into $$\ell$$ numbers $$i_1,\ldots,i_\ell$$, where $$i_j$$ is in the range $$0,\ldots,R(T_{x_{i_j}})$$. If $$i_j = R(T_{x_{i_j}})$$, then the subtree won't contain $$x_{i_j}$$. Otherwise, we can generate a subtree of $$x_{i_j}$$ recursively.

Given the unranking procedure, you can generate a permutation of $$0,\ldots,N-1$$, take the prefix of length $$k$$, and convert it to a list of $$k$$ subtrees. If you have any other way of generating a random sequence of $$k$$ elements of $$0,\ldots,N-1$$ without repetition, then you can use it in the same way.

• This seems like a reasonable solution. It would be nice if the tree could be generated in a way such that there are no collisions though since k is not always that small relative to N. Do you know if this is possible? – anlew Feb 8 '19 at 6:36
• I added an alternative approach using unranking. However, I think you are overestimating the problems created by collisions. The main issue is that you need to keep track of the subtrees that you've already generated. – Yuval Filmus Feb 8 '19 at 6:44
• The unranking procedure was exactly what I was looking for. Although, after thinking more about it, I agree that I might have overestimated the problem caused by collisions. – anlew Feb 8 '19 at 7:52