In the duration of the course, we covered program correctness, proving code by precondition implies postcondition. By this, I wanted to introduce a technique my partner and I worked on for solving question 1 for assignment 2 instead of complete induction. For this episode, I will show the approach of how to create your own code (or my approach) for the ternary tree question.
Question: For arbitrary natural number n, find a (possibly recursive) formula for the number of non-equivalent ternary trees within nodes.
First: Understand the problem
First we have understand that we want to create ternary trees where we won’t have any duplicates trees given n nodes. This seems simple enough. Now I remember being told in highschool that the best way to understand the problem is by visually seeing the problem.
1) Draw cases for 1- 4 nodes (or how many you feel comfortable with to see a pattern).
So you won’t miss any trees, I always start from left to right so create trees manipulating the left subtree first, then the middle and lastly the right subtree by depth (remember this from csc148).
2) Ask yourself before writing your code, “Which coding style(s) would be the easiest for me (recursive, while loops, etc)?”
Second: Devise a Plan
From (2) of understand the problem, we need to put this to good use. Here is where we now need to our visual aspect of the problem and convert that to code. After finishing the cases of drawing, we can see trees of 2 nodes that repeat from 3 nodes. So there should have some recursion in it.
For ex. For trees with 3 nodes. Start with 0 nodes in the left subtree and find all the different combinations of ternary trees you can have. So we can have middle subtree with 2 nodes and right subtree with 0, middle subtree with 1 node and right subtree with 1. Now here is where the recursion comes along. We can find the different number of trees for 0,1 or 2 nodes by using a recursive function. Repeating the process with left subtree having 1 node and once more with 2 nodes. (note: we can’t have left subtree with 3 nodes since it is 3 nodes allowed = 1 (root) + 2). Then find the total.
In order for success in this code, we have to understand and see the pattern which is a combination of trees where you have the root (1 node) and the subtrees total nodes is n-1 nodes, where n is the total number of nodes.
Third: Carrying out the plan
Here is where the actual writing of the code starts to come together. There are a few key points we know already which will help us writing the code.
1) we have to iterate through the possibilities of the subtrees from having 0 nodes in the left subtree to n-1 nodes in the left subtree, where n is the total number of nodes.
2) when iterating, we are finding a combination of trees that we can have without overlapping.
3) since we are using some sort of recursion, we need a base case for nodes of 0 or 1 since there are only 1 possible ternary tree.
Pseudo-code:
# n is number of nodes, L number of node in left subtree (from (1) above)
def ter_tree(n,L):
#if the ternary tree is a tree with 0 or 1 nodes, return 1
#since there is only one possible way of creating a tree with
#0 or 1 nodes (from (3) above)
if n is 0 or 1: return 1
# Stop iterating when n is equal to L. Return 0 since total
# does not change when adding 0.
# total + 0 = total (at end of iterating)
if n is equal to L then stop iterating since n can’t be equal to L:
return 0
# Since each subtree can have n-1 nodes (n nodes minus the root)
# Return every possible subtree with n-1 nodes where the number of
# left(L), middle(M) and right(R) nodes equal to n-1.
# Ex*. Possible subtrees with 2 nodes are (in the form [L,M,R]):
# [[0,0,2],[0,1,1],[0,2,0],[1,0,1],[1,1,0],[2,0,0]]
total = 0
for i in range(n-L):
# the total number of possible ways is the number of
# ways for ternary tree with L nodes times the number
# of ways for ternary tree with i nodes times
# number of ways for ternary tree with n-i-1-L nodes.
# Note: This finds all possible ways with left subtree
# with L nodes and multiplication because
# it is combinations of subtrees.
total += ter_tree(L,0)*ter_tree(i,0)*ter_tree(n-i-1-L,0)
where ter_tree(L,0) will get the possibly trees with L nodes, and the rest of the calls is a manipulation to get the possibly combinations with n-L-1 nodes (i + (n-i-l-L) = n-L-1) and no overlapping.
# When done iterating through for-loop, find all possible ways.
# by making checking the number of ways with L+1 nodes.
# Then return the final number of ways to make a ternary tree
# of n nodes.
return total plus the total from the next possible combination for L+1 nodes in the left subtree with ter_tree(n,L+1)
Fourth: Wrapping Up
As you can see I did slightly half pseudo-code/half actual code. If you understand combinations well (if you are in statistics) then following or tracing your own code and seeing why it does what should be easy. Now what I have is one solution, there are tonnes of other ways to do it, but as long as it follows a double summation format, getting all the right combinations.
Wednesday, December 3, 2008
Subscribe to:
Posts (Atom)