My Math Forum  

Go Back   My Math Forum > High School Math Forum > Probability and Statistics

Probability and Statistics Basic Probability and Statistics Math Forum


Reply
 
LinkBack Thread Tools Display Modes
June 10th, 2013, 02: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!
Pherion is offline  
 
June 13th, 2013, 01: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.
Code2004 is offline  
Reply

  My Math Forum > High School Math Forum > Probability and Statistics

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 07:43 AM
overall min cut separating some node pairs shaon Applied Math 0 December 18th, 2012 05:10 PM
Finding Lowest Common Ancestor Given Parent Node (JAVA) eulerrules1 Computer Science 0 April 10th, 2012 01:00 PM
3 probability ( all need total arrangement possible ) rnck Probability and Statistics 7 November 5th, 2011 09:33 PM
Tricky node joining problem Fibo Applied Math 1 March 26th, 2010 06:32 AM





Copyright © 2019 My Math Forum. All rights reserved.