根据条件在任意嵌套列表中查找组合

Question

我想在有限的点网格上找到可能的路径。比如说，起点是 (x,y)。然后路径中的下一个点 (m,n) 由 conditions

给出

(m!=x) 和 (n!=y) 即。我排除了我之前所在的行和列。
n < y 即。我总是跳下来。
m,n >= 0 即。所有的点总是在第一象限
停止条件是当点位于 x 轴上时。

因此，生成此类 'paths' 可能的所有可能组合。

以下是我试过的。

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) 获得的列表？

编辑 1：

实际上，我从给定的起点（在 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) 将 return (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)]

根据条件在任意嵌套列表中查找组合

find combinations in arbitrarily nested lists under conditions

python

list-comprehension

nested-lists