Dynamic Programming - Print all paths from (0,0) to (n,n) in Grid/Lattice

Question

I'm trying to write an algorithm to print all the paths from point (0,0) to (n,n) in a grid.
The only possible moves are right and up.
Also, you can't move below the diagonal y=x. e.g if you're at (1,1) you can only move to (1,2), but not to (2,1), since it's below the y=x diagonal.

I wrote an algorithm that calculates the number of possible paths from (0,0) to any given (x,y), such that the above limitations are held, but I can't find a way to print out the paths that give these numbers.

The algorithm I wrote is a bottom-up one, as follows:

JUMP(x, y)
1.  M[x-1,y+1] ← 1 
2.  for i=0 to x+1
        M[i,y+1] ← 0
3.  for i=0 to y+1
        M[x+1,i] ← 0
4.  for j=0 to y-1
        for i=j+1 to x
            M[i,j] ← 0

5.  for j=y to 0
        for i=j to 0
            M[i,j] ← M[i+1,j] + M[i,j+1]

6.  return M[i,j]

Please advise on this.

Answer 1

You can solve this problem using a recursive formulation of print all paths from a point $(i,j)$ to the target $(n,n)$ in the grid. I call this function $f(i,j)$. So the all paths will be in $f(0,0)$ call.

$f(i,j) = \begin{cases} \emptyset & if\ \ {i>j}\\ \emptyset & if\ \ \neg( {0\leq i\leq n\ \wedge 0\leq j\leq n) }\\ \{(n,n)\} & if \ \ i = n \wedge j = n\\ \bigcup_{p\,\in\, f(i+1,j)\,\cup\,f(i,j+1) } \ \ \{(i,j)\}\cup p & \text{otherwise} \end{cases}$

By example, two of all paths from $f(0,0)$ when $n=4$ are:

blue path = {{0, 0}, {0, 1}, {1, 1}, {1, 2}, {2, 2}, {2, 3}, {3, 3}, {3, 4}, {4, 4}}

red path = {{0, 0}, {0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}, {4, 4}}

So, although programming is not in the scope of this site, I think is good to see a implementation for a memoization version of the above algorithm. asdf

from functools import wraps

def memo(func):
    cache = {}

    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap

@memo
def f(i, j):
    global n
    if i > j:
        return []
    if not (0 <= i <= n and 0 <= j <= n):
        return []
    if i == n and j == n:
        return [[(n,n)]]
    alls = []
    for path in f(i, j+1)+f(i+1, j):
        if len(path) > 0:
            alls += [[(i,j)] + path] 
    return alls

n = 4
for path in f(0,0):
    print path

Answer 2

In the case of an $x$ by $y$ grid (assuming we start at the bottom-left and travel toward the upper-right), you can notice that every possible path will always contain $x$ steps toward the right and $y$ steps upward. You could encode every possible path with a binary string of length $x+y$ where $0$ encodes "right" and $1$ encodes "up", and there are exactly $x$ $0$'s and exactly $y$ $1$'s in the string.

To solve the problem, you could follow this procedure:

• take a binary string of length $x+y$, starting with all $0$'s
• check if the string has $y$ bits equal to $1$
• if so, print the path the string represents, with $0$ = "right" and $1$ = "up"
• incrememt the binary string by $1$ and repeat

In pseudocode:

x = 7; //the grid is x by y in size
y = 9; 
N = x+y; //length of the binary string

for i from 0 to (2^N)-1:
  if NumberOfOnes(i,N) == y:
    PrintPath(i,N);      

To check if the least-significant bit is a 1, we can just take i mod 2 and check if the result is a 1. We can check bit j in the same way just by bit-shifting j bits to to the right and repeating the processes.

function NumberOfOnes(i,N)
  ones = 0;
  zeroes = 0;
  bit = 0;
  for j from N-1 to 0
    temp = i >> j;     //ensures we read the string from left-to-right
    if (temp mod 2) == 1
     ones++
    else
     zeros++
    if zeros > ones  // this protects us from moving below the diagonal
     ones = -1;
     break;
  return ones

To print the string we use a similar process to find the 1's and let 0 mean "right" and 1 mean "up". We also need to read the string left-to-right.

function PrintPath(i,N)
  path_string = [empty]
  for j from N-1 to 0
    temp = i >> j          //ensures we read the string left-to-right
    if (temp mod 2) == 1
      path_string += 'up, '
    else
      path_string += 'right, '

  print(path_string)

This involves checking $2^{x+y}$ binary numbers and performing $x+y$ bit-shifts on each one.

Also for counting the paths, you can notice that the number of acceptable binary strings is just ${x + y \choose y}/2$ since we have $x+y$ binary digits and need to choose $y$ of them to be $1$, and divide by $2$ to ignore paths below the diagonal.