Python 使用 `yield` 的生成器没有产生预期的结果

Question

我正在尝试查找图中的所有路径。我发现了这个我重现的惊人功能 here:

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)) 会 return [[1], [1,2], [1,2,3], [1,2,4], [1,3]].

我尝试在 path.pop() 行之前添加这一行 if not dead_end: yield list(path)。但这最终会产生一些路径两次并且不会产生单节点路径。我得到的结果是 [[1, 2, 3], [1, 2, 3], [1, 2, 4], [1, 2, 4], [1, 2], [1, 3], [1, 3]] 这不是我想要的！

是否可以修改此代码以生成 "not completed" 路径？你能告诉我怎么做吗？

Answer 1

你就快完成了！首先，您需要提供基本案例。

yield path

您甚至需要在开始迭代之前执行此操作，因为到达第一个 yield 语句意味着您已经 append 编辑了一些内容。

其次，您的重复项来自您的第二个 yield 声明。由于您现在正在 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.

都是相同的

Python 使用 `yield` 的生成器没有产生预期的结果

Python generator using `yield` not producing the desired result

yield

generator

python-3.x