在任意嵌套列表中查找条件下的组合

Question

我想在有限的点网格上找到可能的路径。比如说，起点是(x，y)。然后，根据条件给出路径中的下一点(m，n)。

1. (m!=x)及(n!=y) ie。我不包括我以前所在的行和列。
2. N
3. m，n >= 0.所有的点总是在第一象限。
4. 停止准则是当点位于x轴上时。

因此，生成所有可能的“路径”组合。

以下是我尝试过的。

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

产出：

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

这给出了一个嵌套列表，列出了每个点可能出现的新点。

有人能告诉我如何处理从recurse(1,4)获得的列表吗？

edit1：

实际上，我从一个给定的起点跳(在一个4x4网格有限)，满足上述三个条件，直到满足停止标准，即。m,n > 0

Answer 1

我澄清了我在生成器gridpaths()的文档串中所使用的需求。请注意，我将网格的水平大小作为全局变量，并且网格的垂直大小与此无关，路径点的x坐标可以达到但不超过该全局值，并且非连续路径点的x坐标可以相等(尽管连续路径点必须具有不同的x坐标)。我更改了例程的名称，但保留了这些论点。这个版本的代码增加了对路径上最后一点的y坐标必须为1的要求，而且在接受参数时也更安全。

这是一个列表生成器，所以我的测试代码显示了生成器的大小，然后打印所有的列表。

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)

打印输出显示，4x4网格中的点(1,4)产生48条路径。实际上，gridpaths(x, y)将返回(xsize - 1) * xsize ** (y - 2)路径，这些路径可以非常快地增长。这就是为什么我编写了一个列表生成器，而不是一个列表列表。如果你的要求和我想的不一样，请告诉我。上述代码的打印输出如下：

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