Создать список, используя определенные ключи в dict (python)?

Question

Я реализую алгоритм поиска Дейкстры в Python.В конце поиска я восстанавливаю кратчайший путь, используя карту предшественника, начиная с предшественника узла назначения.Например:

path = []
path.append(destination)
previous = predecessor_map[destination]
while previous != origin:
    path.append(previous)
    previous = predecessor_map[previous]

Есть ли способ сделать это с меньшим количеством строк кода (например, понимание списка)?

Answer 1

Единственное, что я могу предложить, - это избавиться от незначительного дублирования кода:

path = []
previous = destination
while previous != origin:
    path.append(previous)
    previous = predecessor_map[previous]

Кроме того, я думаю, что ваш код на самом деле очень четкий и вряд ли выиграет от любых попыток его сократить.

Наконец, стоит отметить, что вышесказанное также работает, когда destination == origin, тогда как ваша исходная версия, скорее всего, не работает (зависит от того, насколько точно заполнено predecessor_map). Не знаю, относится ли это к вашим случаям использования.

Answer 2

Это может работать:

path = [destination]
path += iter(lambda: predecessor_map[path[-1]], origin)

Он ведет себя так же, как ваш исходный код.Но то, что вы уже написали, прекрасно, как есть.

Если destination может быть равен origin:

path = []
path += iter(lambda: predecessor_map[path[-1]] if path else destination, origin)

Он ведет себя так же, как код @ aix.

Answer 3

def backwalk(mymap, start, origin):
    yield start
    current = mymap[start]
    while current != origin:
        yield current
        current = mymap[current]

path = list(backwalk(predecessor_map, destination, origin))

Это отделяет задачи ходьбы и сбора.

Если вы можете быть уверены, что никогда не начинаете с источника, вы можете упростить до

def backwalk(mymap, start, origin):
    current = start
    while current != origin:
        yield current
        current = mymap[current]

Answer 4

Еще одно возможное решение - использовать программирование в функциональном стиле с отложенным выводом:

from itertools import tee, chain, imap, takewhile

predecessor_map = {2:1, 3:2}
destination = 3
origin = 1

def backwalk(predecessor_map, start, origin):

    def deffered_output():
        for i in output:
            yield i

    result, a = tee(deffered_output())
    b = imap(predecessor_map.get,a)
    output = takewhile(lambda x: x!=origin,chain([start],b))

    return result

print(list(backwalk(predecessor_map,destination,origin)))

Лично я бы не использовал этот подход.Но это интересно для обучения.

Пояснение Ключевой элемент - deferred_output, который откладывает вызовы на outputЗатем мы разбиваем output на 2 итератора, используя tee.Затем мы применяем predecessor_map.get ко второму итератору с именем a и назначаем новому итератору b.Затем мы контролируем выход с помощью takewhile и останавливаемся при достижении origin.

Answer 5

Вы можете рекурсивно пройти по ребрам, предполагая, что predecessor_map является узлом отображения dict на родительский узел и что None является корнем:

predecessor_map={0: None, 1: None, 2: 1, 3: 1, 4: 0, 5: 1}

Определите рекурсивную функцию, которая проходит по дереву вреверс:

def path(node, predecessors):
    return [None] if node is None else [node] + path(predecessors.get(node), predecessors)

Или, если хотите, комбинатор Y:

Y=lambda f: (lambda x: f(lambda *args: x(x)(*args)))(lambda x: f(lambda *args: x(x)(*args)))
path=Y(lambda f: lambda node, p: [None] if node is None else [node] + f(p.get(node), p))

Используется (с использованием списка):

>>> print [node for node in path(None, predecessor_map)]
[None]
>>> print [node for node in path(0, predecessor_map)]
[0, None]
>>> print [node for node in path(1, predecessor_map)]
[1, None]
>>> print [node for node in path(2, predecessor_map)]
[2, 1, None]
>>> print [node for node in path(3, predecessor_map)]
[3, 1, None]
>>> print [node for node in path(4, predecessor_map)]
[4, 0, None]
>>> print [node for node in path(5, predecessor_map)]
[5, 1, None]

Answer 6

Я не думаю, что вы можете сделать эту итерацию с пониманием. Может быть, вы могли бы немного упростить это, например:

    path, previous = [], destination
    while True:
        path.append(previous)
        previous = predecessor_map[previous]
        if previous == origin:
            break

Вышеупомянутый цикл выглядел бы лучше с do..time, но в Python его нет