CODEWITHSUNDEEP
pythonalgorithmiterationdirected-graphtriangle
CWT_Simon
CWT_Simon

Reputation: 13

Finding total amount of paths in a triangle grid (iterative without recursion)

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)

Upvotes: 1

Views: 239

Answers (3)

vvvvv
vvvvv

Reputation: 31619

import math

A = []
def C_iterativ(n):
    C = [[0 for _ in range(n+2)] for _ in range(2*n+1)]
    C[0][0] = 1
    for i in range(2*n+1):
        for j in range(n+1):
            C[i][j] += C[i-1][j-1] + C[i-1][j+1]
    return C[2*n][0]

for i in range(20):
    print(int(1/(i+1)*math.factorial(2*i)/(math.factorial(i)**2)) == C_iterativ(i))

Recursive solution:

def C_memo(i, j, memo={}):
    if (i, j) in memo:
        return memo[(i, j)]
    if i == j == 0:
        result = 1
    elif i == 0 and j > 0:
        result = 0
    elif i > 0 and j == 0:
        result = C_memo(i-1, 1, memo)
    elif i > 0 and j > 0:
        result = C_memo(i-1, j-1, memo) + C_memo(i-1, j+1, memo)
    memo[(i, j)] = result
    return result

This answer was posted as an edit to the question Finding total amount of paths in a triangle grid (iterative without recursion) by the OP CWT_Simon under CC BY-SA 4.0.

Upvotes: 0

Dillon Davis
Dillon Davis

Reputation: 7740

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).

Upvotes: 1

Dave
Dave

Reputation: 9075

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

Upvotes: 0

Related Questions