The puzzle was to generate a random binary tree on n nodes, each structurally distinct tree being equally likely, given a uniform random number generator which can generate a number from 1,2,...,K with probability 1/K, given input of K.
The easier version was to use O(n) calls to the random number generator.
The harder version was to use O(1) calls to the random number generator.
Solution
A structurally unique tree can be encoded by its preorder traversal, which includes the null nodes, and that encoding is reversible.
Using a '1' for a node, and '0' for a null node, we get a string of n 1s and n+1 0s.
For example, just a single node tree encodes are 100. (1 for root, and 0, 0 for the left and right null children), while a tree with a root and its right child encodes as 10100.
An important property of this encoding: Every proper prefix of the encoding has at least as many 1s as 0s, and any string with n 1s and n+1 0s that has that prefix property, is the encoding of a tree.
Now if you look at the reverse of the encoding (e.g: 001 for a single node tree), it is nothing but a semi-balanced string which we encountered in an earlier blog post!
Now we can generate a tree as follows:
Generate a random string of n+1 0s and n 1s. Find the unique semi-balanced string which is a circular shift of that string. Reverse it. Decode to get the tree which gives that preorder.
Thus the problem boils down to picking n numbers out of 2n+1 numbers (the positions of the 1s).
If we use reservoir sampling, this will take O(n) random number calls.
We can also encode the sets to a number from 1 to $\binom{2n+1}{n}$, pick a random number using _one_ random number call (remember it can take arbitrary integers as input), and decode. I will leave the decoding to you.
The easier version was to use O(n) calls to the random number generator.
The harder version was to use O(1) calls to the random number generator.
Solution
A structurally unique tree can be encoded by its preorder traversal, which includes the null nodes, and that encoding is reversible.
Using a '1' for a node, and '0' for a null node, we get a string of n 1s and n+1 0s.
For example, just a single node tree encodes are 100. (1 for root, and 0, 0 for the left and right null children), while a tree with a root and its right child encodes as 10100.
An important property of this encoding: Every proper prefix of the encoding has at least as many 1s as 0s, and any string with n 1s and n+1 0s that has that prefix property, is the encoding of a tree.
Now if you look at the reverse of the encoding (e.g: 001 for a single node tree), it is nothing but a semi-balanced string which we encountered in an earlier blog post!
Now we can generate a tree as follows:
Generate a random string of n+1 0s and n 1s. Find the unique semi-balanced string which is a circular shift of that string. Reverse it. Decode to get the tree which gives that preorder.
Thus the problem boils down to picking n numbers out of 2n+1 numbers (the positions of the 1s).
If we use reservoir sampling, this will take O(n) random number calls.
We can also encode the sets to a number from 1 to $\binom{2n+1}{n}$, pick a random number using _one_ random number call (remember it can take arbitrary integers as input), and decode. I will leave the decoding to you.
No comments:
Post a Comment