Pythonic способ выяснения прямых путей на решетке квадратной решетки?

Я не совсем уверен, как описать мой вопрос здесь, поэтому я думаю, что я попытаюсь объяснить ситуацию в первую очередь. Я получил набор данных из квадратной решетки из 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])]

куда graph[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) и повторять этот процесс до тех пор, пока вы не попадете на другую сторону сетки.

Мне было интересно, был ли более "питонический" способ справиться с этим. Мой собственный код разделен на несколько разных этапов, но я решил, что должен быть какой-то способ сделать это одним махом, а не повторять все так много раз (в настоящее время мне требуется около 60 мс за цикл, чтобы понять все это, и я пытаюсь уменьшить это до 20 мс, если это возможно).

Источник

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
Источник

Возможно, вы захотите взглянуть на этот код:

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)

Хотя это довольно неэффективно, я надеюсь, что вы найдете это полезным.

Источник
Другие вопросы по тегам