在方格网中找出直线路径的Pythonic方法？

Question

我不太确定该怎么描述我的问题，所以我先来解释一下情况。我有一个数据集，是从一个由四边形组成的方格网中提取的。这个方格的大小没有固定的要求。我可以访问描述网格上任意一点邻居的数据（比如，“点236与点417、872、123和331相连”），就这些信息了。

我现在拥有的是这个：

graph = [set([5, 9]), set([4, 11]), set([5, 6, 12]), set([6, 10, 2]), \
         set([1, 3, 8]), set([3, 7, 4]), set([6, 12, 10, 16]), \
         set([5, 9, 18, 12]), set([1, 8, 13]), set([4, 11, 7, 15]), \
         set([2, 10, 17]), set([3, 7, 8, 14]), set([9, 18]), \
         set([18, 12, 16]), set([16, 10, 17]), set([14, 7, 15]), \
         set([15, 11]), set([13, 8, 14])]

在这里，graph[n]让我可以通过索引n访问任何给定点的邻居……整个数据集可以通过下面的二维图形来可视化（我只能通过上面列出的数据来访问这个图形）：

*--------*--------*-------*-------*-------*
| 1      | 5      | 3     | 6     | 4     | 2
|        |        |       |       |       |
|        |        |       |       |       |
*--------*--------*-------*-------*-------*
| 9      | 8      | 12    | 7     | 10    | 11
|        |        |       |       |       |
|        |        |       |       |       |
*--------*--------*-------*-------*-------*
  13       18       14      16      15      17

我想把它转化成看起来像这样的数据：

u = [[1, 5, 3, 6, 4, 2], [9, 8, 12, 7, 10, 11], [13, 18, 14, 16, 15, 17]]
v = [[1, 9, 13], [5, 8, 18], [3, 12, 14], [6, 7, 16], [4, 10, 15], [2, 11, 17]]

输出数据描述了网格的平行线（从索引号最小的角落开始）。每个点都有一个唯一的索引，网格的索引是连续的（在这个例子中是从1到18），但顺序没有任何保证。网格的尺寸是事先不知道的。每个点的连接数只能是2（角落点）、3（边缘点）或4（中心点）。

现在，我写了一个暴力破解的方法来处理这个问题，但效率不高。这个方法是先找出前两个水平和垂直的边（在这个例子中是[1, 5, 3, 6, 4, 2]和[1, 9, 13]），然后通过获取每个点的连接邻居并从中减去已经访问过的点来“移动”每条边（比如1 -> 5，9 -> 8，13 -> 18），重复这个过程直到到达网格的另一边。

我在想是否有更“pythonic”的方法来处理这个问题。我的代码分成了几个不同的阶段，但我觉得应该有办法一次性完成，而不是这么多次地迭代（目前每次运行大约需要60毫秒，我希望能把这个时间缩短到20毫秒）。

Answer 1

你可能想看看这段代码：

def lattice_paths_of_n(n):
    list2 = []
    my_list = []
    for i in range(1, n+2):
        list2.append(i)
    for i in range(1, n+2):
        my_list.append(list2)
    for i in range(0,n+1):
        for f in range(0,n+1):
            if f == 0 or i == 0:
                my_list[i][f] = 1
            else:
                my_list[i][f] = my_list[i-1][f]+my_list[i][f-1]
    return my_list[n][n]
import math
start_time = time.time()
print(lattice_paths_of_n(20))
print(time.time()-start_time)

虽然这段代码效率不高，但我希望你觉得它有用。

Answer 2

我觉得你可以一步一步地构建你的网格，每次处理一个节点，这样不会太麻烦。以下是我建议的做法：

1. 从任意一个角落节点开始，你可以通过它只有两个邻居来识别它。
2. 找到一条边（哪条都可以），选择你起始节点的一个邻居，然后不断移动到一个有三个邻居的节点（而不是四个），同时避免回到上一个节点。最后的情况是你到达另一个角落节点。
3. 遍历你刚找到的这一行，取出每个节点剩下的邻居。每个节点只剩下一个邻居（不在网格里的），所以这里没有复杂的地方。
4. 重复第3步，直到你到达最远的边。
5. 通过转置列表来创建你的第二个列表（列），比如用 zip(*rows)。

如果你的邻居数据是以字典的形式存在，映射每个节点到它的邻居列表，这段代码应该可以工作：

def make_grid(neighbor_dict):
    # step 1, find the first corner
    for node, neighbors in neighbor_dict:
        if len(neighbors) == 2:
            break  # node and neighbors will hold our start corner and its neighbors

    # step 2, build the first edge
    row = [node, neighbor[0]]  # start with the corner, and an arbitrary neighbor
    while len(neighbors_dict[row[-1]]) == 3:
        for neighbor in neighbor_dict[row[-1]]:
            if neighbor != row[-2] and len(neighbor_dict[neighbor]) <= 3:
                row.append(neighbor)
                break

    # setup for steps 3 and 4
    seen = set(row)  # a set of all nodes we've added to the grid so far
    rows = []
    done = False

    while not done:  # this loop is step 4, building all rows
        rows.append(row)
        new_row = []
        for node in row:  # this is step 3, building a new row from the previous row
            for neighbor in neighbor_dict[node]:
                if neighbor not in seen:
                    new_row.append(neighbor)
                    seen.add(neighbor)
                    break
            else:  # no break hit in for loop, only happens if `row` is the far edge
                done = True
                break
        row = new_row

    # step 5, transpose to get columns from rows
    columns = list(zip(*rows))

    return rows, columns