使用`yield`的Python生成器未产生期望的结果

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))返回[[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]]，这不是我想要的！

是否可以修改此代码以产生“未完成”的路径？你能建议我怎么做吗？

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，第一个元素都相同。