Генератор Python с использованием `yield` не дает желаемого результата - PullRequest
Новая
       51

Генератор Python с использованием `yield` не дает желаемого результата

0 голосов
/ 04 мая 2020

Я пытаюсь найти все пути на графике. Я нашел эту удивительную функцию, которую я воспроизводил здесь : 

def paths(graph, v):
    """Generate the maximal cycle-free paths in graph starting at v.
    graph must be a mapping from vertices to collections of
    neighbouring vertices.

    >>> g = {1: [2, 3], 2: [3, 4], 3: [1], 4: []}
    >>> sorted(paths(g, 1))
    [[1, 2, 3], [1, 2, 4], [1, 3]]
    >>> sorted(paths(g, 3))
    [[3, 1, 2, 4]]

    """
    path = [v]                  # path traversed so far
    seen = {v}                  # set of vertices in path
    def search():
        dead_end = True
        for neighbour in graph[path[-1]]:
            if neighbour not in seen:
                dead_end = False
                seen.add(neighbour)
                path.append(neighbour)
                yield from search()
                path.pop()
                seen.remove(neighbour)
        if dead_end:
            yield list(path)
    yield from search()

Однако, как показывает информация, представленная в функции, эта функция возвращает пути, которые завершились, то есть попали в тупик , Я хотел бы изменить функцию для получения неполных путей, чтобы sorted(paths(g,1)) возвращал [[1], [1,2], [1,2,3], [1,2,4], [1,3]].

Я попытался добавить эту строку if not dead_end: yield list(path) перед строкой, которая говорит path.pop(). Но это приводит к тому, что несколько путей приводят к двум путям и не дают пути к одному узлу. Результат, который я получил, был [[1, 2, 3], [1, 2, 3], [1, 2, 4], [1, 2, 4], [1, 2], [1, 3], [1, 3]], что не то, что я хочу!

Можно ли изменить этот код, чтобы получить "незавершенные" пути? Не могли бы вы посоветовать мне, как go об этом?

1 Ответ

1 голос
/ 04 мая 2020

Ты почти у цели! Во-первых, вам нужно указать базовый случай. 

yield path

Это нужно сделать еще до того, как вы начнете выполнять итерации, поскольку переход к первому выражению yield означает, что вы уже append ed что-то.

Во-вторых, ваши дубликаты исходят от вашего второго yield заявления. Поскольку теперь вы выполняете итерацию, вы можете полностью удалить ее. Кроме того, поскольку мы знаем if neighbour not in seen:, мы не достигли тупика и, следовательно, dead_end является избыточным, и мы можем его удалить.

Итак, в итоге: 

def paths(graph, v):
    """Generate the maximal cycle-free paths in graph starting at v.
    graph must be a mapping from vertices to collections of
    neighbouring vertices.

    >>> g = {1: [2, 3], 2: [3, 4], 3: [1], 4: []}
    >>> sorted(paths(g, 1))
    [[1, 2, 3], [1, 2, 4], [1, 3]]
    >>> sorted(paths(g, 3))
    [[3, 1, 2, 4]]

    """
    path = [v]                  # path traversed so far
    seen = {v}                 # set of vertices in path
    yield path

    def search():
        for neighbour in graph[path[-1]]:
            if neighbour not in seen:
                seen.add(neighbour)
                path.append(neighbour)
                yield from search()

                yield list(path)

                path.pop()
                seen.remove(neighbour)
    yield from search()

g = {1: [2, 3], 2: [3, 4], 3: [1], 4: []}

print(sorted(paths(g, 1)))
print(sorted(paths(g, 3)))

Кроме того, sorted() можно обменять на list(), поскольку первый элемент будет идентичным для каждого полученного list.

...