
Probability and Statistics Basic Probability and Statistics Math Forum 
 LinkBack  Thread Tools  Display Modes 
June 10th, 2013, 01:49 PM  #1 
Newbie Joined: Jun 2013 Posts: 1 Thanks: 0  Total Possibilities of a Probability Tree (with node reuse)
Hello Everyone! It's been a while since I've done any hard core probability, and I'm working on a program to help my friend randomly generate phrases from snippets of text. The program is fine, I just want to be able to calculate the total possible outcomes from a web of phrases. Here's a link to an example tree that I drew to try and figure this out: http://arolkay.com/Tree.gif. At first I tried to work from the top down, and multiply every time I reached a branching node, but I either am not keeping track properly, or something else is happening and I'm always ending up with way too much. Then I started from the bottom up, and I got closer, but was one off (the actual number of possibilities is 12, and I got 11). I'm using Java to write this program, so I'm guessing I'll be using a recursive function to plow through the whole tree. Any ideas on how to calculate this would be greatly appreciated! 
June 13th, 2013, 12:01 AM  #2 
Senior Member Joined: Jan 2013 Posts: 113 Thanks: 0  Re: Total Possibilities of a Probability Tree (with node reu
Starting with the root node, traverse the tree downwards by selecting the first available succeeding node. When you reach a node with no successors, you have found a path. When you have found a path, traverse the tree upwards along the same path by which you arrived. Stop at each node to see if there are any successors which have not yet been accessed. If you find an available successor, traverse it downwards by selecting the first available succeeding node. When you reach a node with no successors, another path has been found. Continue this procedure until you end at the start node with no available successors. CASE EXAMPLE: For brevity, a node is defined by X(S), where X is the node name and S is the set of successors. Let the node set be: Where S is the start node. Here's a trace.  Current: S. Travel: A. Reason: first available.  Current: A. Travel: C. Reason: first available.  Current: C. Travel: A. Reason: end of branch; retracing path. (1)  Current: A. Travel: S. Reason: no unused successors; retracing path.  Current: S. Travel: B. Reason: unused successor.  Current: B. Travel: C. Reason: first available.  Current: C. Travel: B. Reason: end of branch; retracing path. (2)  Current: B. Travel: D. Reason: unused successor.  Current: D. Travel: E. Reason: first available.  Current: E. Travel: D. Reason: end of branch; retracing path. (3)  Current: D. Travel: B. Reason: no unused successors; retracing path.  Current: B. Travel: S. Reason: no unused successors; retracing path.  Current: S. Travel: halt. Reason: no unused successors at root node. 

Tags 
node, possibilities, probability, reuse, total, tree 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Use a tree diagram to calculate the probability  alfred_oh  Advanced Statistics  0  May 3rd, 2013 06:43 AM 
overall min cut separating some node pairs  shaon  Applied Math  0  December 18th, 2012 04:10 PM 
Finding Lowest Common Ancestor Given Parent Node (JAVA)  eulerrules1  Computer Science  0  April 10th, 2012 12:00 PM 
3 probability ( all need total arrangement possible )  rnck  Probability and Statistics  7  November 5th, 2011 08:33 PM 
Tricky node joining problem  Fibo  Applied Math  1  March 26th, 2010 05:32 AM 