# Iterating through every path of a Trinomial Tree

I am attempting to come up with an algorithm to iterate through every possible path of a trinomial tree and am having difficulties coming up with one. Is there any literature on this or has anyone else written something similar?

To be specific I am trying to calculate the P&L of stock trades from node 0 to every possible path end.

EDIT: Let me clarify - for a 1 step trinomial tree there are three paths: 1 (up) 0 (middle) or -1 (down). Adding another step makes the tree have 5 ending points and 9 paths: 11 (up,up) 10 (up,mid) 01 (mid, up) 1-1 (up,down) 00 (mid,mid) -11 (down,up) 0-1 (m,d) -10 (d,m) -1-1 (d,d)

I am aware the total number of paths that end at a given point is given by Pascal's tetrahedron but I do not know how to come up with all the paths for an arbitrary (n-step) tree. So I need the 1,-1,1,-1,0 sequence which in this case would end on the middle node of a 5 step tree.

-
Like a depth-first search? –  chrisaycock Apr 9 '13 at 2:43
Can you describe the data structure of your tree? Is the tree recombining? –  Bob Jansen Apr 9 '13 at 12:40
So you want to condition on a specific path end? –  Quartz Apr 9 '13 at 16:20

If I understand you correctly, here's an example in Python. Any other programming language should be able to do something similar:

def search(path):
if len(path) == 5:
if sum(path) == 0:
print path
else:
search(path+[1])
search(path+[0])
search(path+[-1])


Just invoke it with an empty array:

>> search([])
[1, 1, 0, -1, -1]
[1, 1, -1, 0, -1]
[1, 1, -1, -1, 0]
[1, 0, 1, -1, -1]
[1, 0, 0, 0, -1]
[1, 0, 0, -1, 0]
[1, 0, -1, 1, -1]
[1, 0, -1, 0, 0]
[1, 0, -1, -1, 1]
[1, -1, 1, 0, -1]
[1, -1, 1, -1, 0]
[1, -1, 0, 1, -1]
[1, -1, 0, 0, 0]
[1, -1, 0, -1, 1]
[1, -1, -1, 1, 0]
[1, -1, -1, 0, 1]
[0, 1, 1, -1, -1]
[0, 1, 0, 0, -1]
[0, 1, 0, -1, 0]
[0, 1, -1, 1, -1]
[0, 1, -1, 0, 0]
[0, 1, -1, -1, 1]
[0, 0, 1, 0, -1]
[0, 0, 1, -1, 0]
[0, 0, 0, 1, -1]
[0, 0, 0, 0, 0]
[0, 0, 0, -1, 1]
[0, 0, -1, 1, 0]
[0, 0, -1, 0, 1]
[0, -1, 1, 1, -1]
[0, -1, 1, 0, 0]
[0, -1, 1, -1, 1]
[0, -1, 0, 1, 0]
[0, -1, 0, 0, 1]
[0, -1, -1, 1, 1]
[-1, 1, 1, 0, -1]
[-1, 1, 1, -1, 0]
[-1, 1, 0, 1, -1]
[-1, 1, 0, 0, 0]
[-1, 1, 0, -1, 1]
[-1, 1, -1, 1, 0]
[-1, 1, -1, 0, 1]
[-1, 0, 1, 1, -1]
[-1, 0, 1, 0, 0]
[-1, 0, 1, -1, 1]
[-1, 0, 0, 1, 0]
[-1, 0, 0, 0, 1]
[-1, 0, -1, 1, 1]
[-1, -1, 1, 1, 0]
[-1, -1, 1, 0, 1]
[-1, -1, 0, 1, 1]

-
Yea that looks like what I want I will extend it to loop through every possible ending point. I am not familiar with Python and can't seem to figure out what the statement path+[1] does. I am trying to implement this in c++ and it I am unsure how your code would do anything else besides add an element to an array with a 1 in it until there are 5 and then stop. Thanks again. –  user2183336 Apr 9 '13 at 18:16
@user2183336 That Python notation is the side-effect free way of appending an element. Ie, it returns a new array without modifying the original. Again, the key point to my example is that this is a depth-first search; I recursively descend each possible path. The array notation I used in Python was just for convenience; the DFS is how I actually solved the problem. –  chrisaycock Apr 9 '13 at 18:21
Great. Thanks a lot I appreciate it. –  user2183336 Apr 9 '13 at 18:30

To convert an index to base 3 (actually to an array with the base 3 digits, each one selecting a move up/mid/down) you only need to alternate a modulo-3 (remainder) operator and integer division by 3. Or were you asking for something else?

-