Python

Question

我的计划目标如下：

给定任何形状（表示为枚举点及其与其他点的连接），return一个列表包含所有可能的路径（如strings/lists/...）。路径是给定形状的 'drawing'，其中：

没有使用连接不止一次和

'pen' 尚未解除（示例如下）。

下面的代码基本上是我到目前为止所想出的。这不是实际程序的代码，但基本语义是相同的（即，如果这段代码可以工作，我的程序也可以工作）。

"""
Example used:

    2
   / \
  /   \
 /     \
1-------3
"""


from copy import deepcopy

points = {1: [2,3],
          2: [1,3],
          3: [1,2]}

def find_paths(prev_point, points):
    for current_point in points[prev_point]:
        points[current_point].remove(prev_point)
        points[prev_point].remove(current_point)
        return [prev_point] + find_paths(current_point, points)
    return [prev_point]

def collect(points):
    results = []
    for first_point in points:
        result = find_paths(first_point, deepcopy(points))
        results.append(result)
    return results

print(collect(points))

我一直在努力实现 return 所有路径。 截至目前，它仅列出了 3 个（出6).我确实知道问题出在 f 中的 for 循环每次被调用时恰好执行一次（并且被调用 3 次），因为执行被 [=14= 终止] 每一次。但是，到目前为止，我一直没能找到避免这种情况的方法——我试着让 f 成为一个生成器，但这给了我一个生成器列表作为最终结果，无论我如何尝试改变它.

感谢任何帮助！

编辑：我只是将 find_paths 中的 return 替换为 yield 的生成器版本。所以最后两行看起来像：

... yield [prev_point] + find_paths(current_point, points) yield [prev_point]

此外，我尝试了一个 'flattener' 生成器，但它根本不起作用：

def 展平（x）：如果可调用（x）：对于我在 x 中：收益率趋于平缓（i）产量 x</p> <p>定义函数（）：产量 1 lis = [1,2,func]</p> <p>对于扁平化中的 f(lis)：打印(f)

Answer 1

我认为以下内容有效。我基于你的原始代码，但做了一些事情（有些是必要的，有些不是）：

重命名 find_paths 中的参数，使之对我更有意义。我们正在使用 current_point 而不是 previous_point，等等
添加结束条件以停止递归。
为正在生成的每条可能路径复制点，并return（产生）每条可能路径。您的原始代码没有这方面的逻辑，因为它每次调用 find_paths 只期望一个结果，但是在像这样使用递归时这实际上没有意义。出于同样的原因，我也 extend 我的最终结果。

代码如下：

from copy import deepcopy

points = {1: [2,3],
          2: [1,3],
          3: [1,2]}


def find_paths(current_point, points):
    if len(points[current_point]) == 0:
        # End condition: have we found a complete path? Then yield
        if all(not v for v in points.values()):
            yield [current_point]
    else:
        for next_point in points[current_point]:
            new_points = deepcopy(points)
            new_points[current_point].remove(next_point)
            new_points[next_point].remove(current_point)
            paths = find_paths(next_point, new_points)
            for path in paths:
                yield [current_point] + path


def collect(points):
    results = []
    for first_point in points:
        result = find_paths(first_point, points)
        results.extend(list(result))
    return results

print(collect(points))

结果：

[1, 2, 3, 1]
[1, 3, 2, 1]
[2, 1, 3, 2]
[2, 3, 1, 2]
[3, 1, 2, 3]
[3, 2, 1, 3]

您的原始示例图片应适用于以下内容：

points = {
    1: [2,3],
    2: [1,3,4,5],
    3: [1,2,4,5],
    4: [2,3,5],
    5: [2,3,4],
    }

编辑： 删除了我在 collect.

中的额外深层复制

每次都需要复制points，因为你是"saving"当前路径的当前状态你是"drawing"。如果您没有复制它，那么沿着路径到达节点 2 将在沿着路径到达节点 3 时更改点的状态。

Python - 找到任意形状点之间的所有路径

Python - finding all paths between points of arbitrary shape

graph-theory

generator

nodes