i have a given a triangle grid:

Triangle

For every point (i,j) with i j being even:

Given recursive function

Now i need to write a iterative function that finds all possible paths from (0,0) to the point (2n,0) given that n ∈ N.

So my idea, written in pseudo code:

def path (i,j):
       
    paths = set()
    A = [ 1 for  x in range(j)]
    
    for x in range (i - len(A)):
          A.append (last)-(-1)
          A.append (-1)
    set.append(path)
 
    for i in range (i!):
          candidate = permutate(A)
          for i in range(len(A)):
              if sum (A [1: i]) < 0
                  break
          Paths.append(candidate)
    return len(paths)

i need to count the total amount of paths possible to (2n,0)

CodePudding user response：

On a more mathy note, this problem is equivalent to a more famous problem- balancing parenthesis. Ever step up-right is a ( and ever step down-right is a ), with n parenthesis pairs, how many valid sequences of parenthesis are there?

The answer for n is the nth catalan number, which is nck(2n, n) - nck(2n, n 1) (nck being "n choose k"). In python, this comes out to-

from math import comb

def catalan(n):
    return comb(2*n, n) - comb(2*n, n 1)

So the answer to "How many distinct shortest paths from (0, 0) to (2n, 0) through my triangular grid are there?" is catalan(n).

CodePudding user response：

For every node other than (0,0), the number of ways to reach that node is the sum of the number of ways to meet its immediate predecessors. There is one way to reach (0,0).

Start with (0,0) -> 1, and a queue containing (1,1). On each iteration, take the node at the front of the queue, update it to be the sum of its predecessors, and add any successors that have all predecessors calculated to the end of the queue.

(0,0) -> 1; queue = [(1,1)]
(1,1) -> 1; queue = [(2,2), (2,0)]
(2,2) -> 1; queue = [(2,0), (3,3)]
(2,0) -> 1; queue = [(3,3), (3,1)]
(3,3) -> 1; queue = [(3,1), (4,4)]
(3,1) -> 2; queue = [(4,4), (4,0), (4,2)]
... and so on