find combinations in arbitrarily nested lists under conditions

Question

I want to find possible paths on a finite grid of points. Say, starting point is (x,y). Then next point (m,n) in the path is given by conditions

1. (m!=x) and (n!=y) ie. I exclude the row and column I was in previously.
2. n < y ie. I always hop DOWN.
3. m,n >= 0 ie. all the points are always in first quadrant
4. Stopping criteria is when a point lies on x axis.

Hence, generate all possible combinations of such 'paths' possible.

Following is what I've tried.

def lisy(x,y):
    return [(i,j) for i in range(4,0,-1) for j in range(4,0,-1) if(i!=x and j<y)]

---

def recurse(x,y):
    if (not lisy(x,y)):
        return (x,y)
    else:
        return [(x,y), [recurse(i,j) for i,j in lisy(x,y)]]

---

OUTPUT:

In [89]: recurse(1,4)
Out[89]: 
[(1, 4),
 [[(4, 3),
   [[(3, 2), [(4, 1), (2, 1), (1, 1)]],
    (3, 1),
    [(2, 2), [(4, 1), (3, 1), (1, 1)]],
    (2, 1),
    [(1, 2), [(4, 1), (3, 1), (2, 1)]],
    (1, 1)]],
  [(4, 2), [(3, 1), (2, 1), (1, 1)]],
  (4, 1),
  [(3, 3),
   [[(4, 2), [(3, 1), (2, 1), (1, 1)]],
    (4, 1),
    [(2, 2), [(4, 1), (3, 1), (1, 1)]],
    (2, 1),
    [(1, 2), [(4, 1), (3, 1), (2, 1)]],
    (1, 1)]],
  [(3, 2), [(4, 1), (2, 1), (1, 1)]],
  (3, 1),
  [(2, 3),
   [[(4, 2), [(3, 1), (2, 1), (1, 1)]],
    (4, 1),
    [(3, 2), [(4, 1), (2, 1), (1, 1)]],
    (3, 1),
    [(1, 2), [(4, 1), (3, 1), (2, 1)]],
    (1, 1)]],
  [(2, 2), [(4, 1), (3, 1), (1, 1)]],
  (2, 1)]]

This gives me a nested lists of possible new points from each point.

Can anyone tell me how to process my list obtained from recurse(1,4)?

edit1:

Effectively I hop from a given starting point (in a 4x4 grid [finite]), satisfying the three conditions mentioned until stopping criteria is met, ie. m,n > 0

Answer 1

I clarify the requirements I am working under in the docstring of my generator gridpaths(). Note that I have the horizontal size of the grid as a global variable and the vertical size of the grid is irrelevant, the x-coordinates of path points can be up to but not exceed that global value, and x-coordinates of non-consecutive path points can be equal (though consecutive path points must have different x-coordinates). I changed the name of the routine but kept the arguments as you had them. This version of my code adds the requirement that the y-coordinate of the final point on the path must be 1, and it also is safer in accepting arguments.

This is a generator of lists, so my test code shows how large the generator is then prints all the lists.

def gridpaths(x, y):
    """Generate all paths starting at (x,y) [x and y must be positive
    integers] where, if (m,n) is the next point in the path after
    (x,y), then m and n are positive integers, m <= xsize [xsize is a
    global variable], m != x, and n < y, and so on for all consecutive
    path points. The final point in the path must have a y-coordinate
    of 1. Paths are yielded in lexicographic order."""
    def allgridpaths(x, y, pathsofar):
        """Generate all such paths continuing from pathssofar without
        the y == 1 requirement for the final path point."""
        newpath = pathsofar + [(x, y)]
        yield newpath
        for m in range(1, xsize+1):
            if m != x:
                for n in range(1, y):
                    for path in allgridpaths(m, n, newpath):
                        yield path
    x, y = max(int(x), 1), max(int(y), 1)  # force positive integers
    for path in allgridpaths(x, y, []):
        # Only yield paths that end at y == 1
        if path[-1][1] == 1:
            yield path

# global variable: horizontal size of grid
xsize = 4

print(sum(1 for p in gridpaths(1, 4)), 'paths total.')
for p in gridpaths(1, 4):
    print(p)

The printout shows that the point (1,4) in a 4x4 grid yields 48 paths. In fact, gridpaths(x, y) will return (xsize - 1) * xsize ** (y - 2) paths, which can grow very quickly. That is why I programmed a generator of lists rather than a list of lists. Let me know if your requirements are different from what I suppose. The printout from that code above is:

48 paths total.
[(1, 4), (2, 1)]
[(1, 4), (2, 2), (1, 1)]
[(1, 4), (2, 2), (3, 1)]
[(1, 4), (2, 2), (4, 1)]
[(1, 4), (2, 3), (1, 1)]
[(1, 4), (2, 3), (1, 2), (2, 1)]
[(1, 4), (2, 3), (1, 2), (3, 1)]
[(1, 4), (2, 3), (1, 2), (4, 1)]
[(1, 4), (2, 3), (3, 1)]
[(1, 4), (2, 3), (3, 2), (1, 1)]
[(1, 4), (2, 3), (3, 2), (2, 1)]
[(1, 4), (2, 3), (3, 2), (4, 1)]
[(1, 4), (2, 3), (4, 1)]
[(1, 4), (2, 3), (4, 2), (1, 1)]
[(1, 4), (2, 3), (4, 2), (2, 1)]
[(1, 4), (2, 3), (4, 2), (3, 1)]
[(1, 4), (3, 1)]
[(1, 4), (3, 2), (1, 1)]
[(1, 4), (3, 2), (2, 1)]
[(1, 4), (3, 2), (4, 1)]
[(1, 4), (3, 3), (1, 1)]
[(1, 4), (3, 3), (1, 2), (2, 1)]
[(1, 4), (3, 3), (1, 2), (3, 1)]
[(1, 4), (3, 3), (1, 2), (4, 1)]
[(1, 4), (3, 3), (2, 1)]
[(1, 4), (3, 3), (2, 2), (1, 1)]
[(1, 4), (3, 3), (2, 2), (3, 1)]
[(1, 4), (3, 3), (2, 2), (4, 1)]
[(1, 4), (3, 3), (4, 1)]
[(1, 4), (3, 3), (4, 2), (1, 1)]
[(1, 4), (3, 3), (4, 2), (2, 1)]
[(1, 4), (3, 3), (4, 2), (3, 1)]
[(1, 4), (4, 1)]
[(1, 4), (4, 2), (1, 1)]
[(1, 4), (4, 2), (2, 1)]
[(1, 4), (4, 2), (3, 1)]
[(1, 4), (4, 3), (1, 1)]
[(1, 4), (4, 3), (1, 2), (2, 1)]
[(1, 4), (4, 3), (1, 2), (3, 1)]
[(1, 4), (4, 3), (1, 2), (4, 1)]
[(1, 4), (4, 3), (2, 1)]
[(1, 4), (4, 3), (2, 2), (1, 1)]
[(1, 4), (4, 3), (2, 2), (3, 1)]
[(1, 4), (4, 3), (2, 2), (4, 1)]
[(1, 4), (4, 3), (3, 1)]
[(1, 4), (4, 3), (3, 2), (1, 1)]
[(1, 4), (4, 3), (3, 2), (2, 1)]
[(1, 4), (4, 3), (3, 2), (4, 1)]