python - 旅行推销员:递归获取所有可能的路径

我正在尝试编写一种递归方法来计算旅行商问题的所有可能路径：

def allPaths(toCover, path=""):

    path = path + toCover[0]
    toCover.remove(toCover[0])

    if len(toCover)>0:
        for x in range (0, len(toCover)):
            #swop cities
            temp = toCover[0]
            toCover[0] = toCover[x]
            toCover[x] = temp
            allPaths(toCover, path)
    else :
        print path


cities = ["A", "B", "C", "D"]

allPaths(cities)

所以，我有一个城市清单。

我将列表中的第一个城市添加到当前路径。
我从城市toCover列表中删除添加的城市。
对于列表中每个剩余的城市，我再次调用allPaths()函数。我修改列表参数，每个城市在索引0上一次。

（我想用以下列表实例调用allPath：

[B,C,D]
[C,B,D]
[D,C,B]

）

但是，当我调试它时，在allPath的所有“实例”中都会修改“ citys- toCover”列表。这意味着它将返回第一个有效路径“ ABCD”，但不会继续，因为对于下一个调用，所有城市都已被删除。

我究竟做错了什么？

我希望这个解释很清楚...

最佳答案

解决方案很容易。这是因为toCover（如果您问我，应将其命名为to_cover，但这是您的代码^^）是一个列表。
列表是可变的，这意味着每个实例都拥有对原始对象的引用，从而导致所有更改都是在所有引用上进行的（好吧，它们实际上只是对对象完成了，但是引用指向了该对象，所以...）。

您可以通过三种方式解决它：


而是使用元组，或者仅使用列表就好像它是元组一样

将cities = ["A", "B", "C", "D"]替换为cities = ("A", "B", "C", "D")（如果要使用元组），并使用toCover = toCover[1:]而不是toCover.remove(toCover[0])，则应始终为（如果它应修改基础对象）del toCover[0]。

x[1:]创建一个列表或元组的切片（尽管您可以使用自己的类型为该运算符实现几乎任何东西），从而导致一个新实例具有除第一个元素外的任何元素。参见here（python文档缺乏真正的解释，不要问我为什么）。
一遍又一遍地复制列表

这种解决方案是解决问题的常用方法，但实际上并非解决之道。这样可以通过复制如下列表来绕过引用：toCover = toCover[:]（应位于函数的顶部）。它创建一个包含整个列表的切片（再次：this link），有效地进行复制。
使用itertools.permutations wich可以完成您想做的事情。 （请参阅@John Coleman对您的问题的评论）有关更多详细信息，请参见python documentation。


我希望我能帮上忙，

代号Lambda