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

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

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

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

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

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

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..

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]

Вы можете рекурсивно перемещаться по ребрам, предполагая, что 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]

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

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.

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

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

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