Counting pairs of non-edge-intersecting lattice paths.

nonintersecting_lattice_paths.py

def init_4d(n):
    return [[[[0 for i in range(n)]
              for j in range(n)]
             for k in range(n)]
            for l in range(n)]

def recurrence(c,x1,y1,x2,y2):
    total = 0
    # These two cases are always valid; even if the two paths have met at
    # (x1,y1), then in these cases the previous step cannot be the same, so
    # they do not share an edge.
    if x1 > 0 and y2 > 0:
        total += c[x1-1][y1][x2][y2-1]
    if y1 > 0 and x2 > 0:
        total += c[x1][y1-1][x2-1][y2]

    # These two cases are more dangerous.
    if x1 != x2 or y1 != y2:
        if x1 > 0 and x2 > 0:
            total += c[x1-1][y1][x2-1][y2]
        if y1 > 0 and y2 > 0:
            total += c[x1][y1-1][x2][y2-1]

    c[x1][y1][x2][y2] = total
    return total

def compute_n( n ):
    c = init_4d(n)
    for x1 in range(n):
        for y1 in range(n):
            for x2 in range(n):
                for y2 in range(n):
                    if x1 == 0  and y1 == 0 and x2 == 0 and y2 == 0:
                        c[x1][y1][x2][y2] = 1                        
                    else:
                        recurrence(c,x1,y1,x2,y2)
    #print( c )
    return c[n-1][n-1][n-1][n-1]