0

我不太确定如何在这里描述我的问题，所以我想我会先尝试解释一下情况。我有一个从 4 边多边形的方形格子网格中提取的数据集。不能保证晶格尺寸是特别的。我可以访问描述网格上任何给定点的邻居的数据（即“点 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])]

Wheregraph[n]让我可以通过索引访问任何给定点的邻居n......整个数据集可以通过下面显示的 2D 图表进行可视化（我无法通过上面列出的数据访问其他数据）：

*--------*--------*-------*-------*-------*
| 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 毫秒）。

4

2 回答 2

0

I think you can build your grid gradually, one node at a time without too much trouble. Here's how I'd do it:

  1. Start with any corner node, which you can detect by it only having two neighbors.
  2. Find one edge (it doesn't matter which) by picking either of your start node's neighbors and then repeatedly moving on to a neighbor with exactly three neighbors of its own (rather than four), avoiding going back to the previous node. The end case is when you get to another corner.
  3. Loop over the row you just found, taking the remaining neighbor of each node. There's only one neighbor node left (that's not already in the grid) so there's no complexity here.
  4. Repeat step 3 until you get to the far edge.
  5. Make your second list (of the columns) by transposing the lists (e.g. with zip(*rows))

If your neighbor data is in the form of a dictionary mapping from each node to a list of its neighbors, this code should work:

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
于 2014-06-06T05:45:49.307 回答
0

你可能想看看这段代码：

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)

虽然效率很低，但我希望你觉得它有用。

于 2016-05-20T02:58:59.220 回答