Traveling Salesman: Get all possible Paths with recursion

I am trying to write a recursion method to calculate all possible paths of the traveling salesman problem:

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)

So, I have a list of cities.

I add the first city in the list to the current path. I remove the added city from the cities toCover list. For each remaining city in the list I call the allPaths() function again. I modify the list parameter, that each city is on index 0 once.

(I want call the allPaths with the following list instances:

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

)

However, when I am debugging this, the cities-toCover list gets modified across all "instances" of allPaths. Which means, it returns the first valid path "ABCD", but then does not continue because for the next call, all cities have already been removed.

What am I doing wrong?

I hope this explanation is some what clear...

The solution is easy. It's because toCover (wich should be named to_cover, if you ask me, but hey, it's your code ^^) is a list. Lists are mutable, that means that every instance holds a reference to the original object, resulting in the problem that all changes are done on all references (ok, they are really just done to the object, but the references point to that object, so...).

You can solve it in three ways:

• Using a tuple instead, or just using the list as if it was a tuple

  You replace cities = ["A", "B", "C", "D"] with cities = ("A", "B", "C", "D") (if you want a tuple), and use toCover = toCover[1:] instead of toCover.remove(toCover[0]), wich should be (if it should modify the underlying object) del toCover[0] anyway.

  x[1:] creates a slice of a list or a tuple (although you can implement almost anything for that operator in your own types), resulting in a new instance that has any element except the first one. See here (the python documentation lacks a real explanation, don't ask me why).

• Duplicating the list over and over again

  This solution is the common way to deal with the problem, but it really isn't the way to go here. This gets around the reference by copying the list like this: toCover = toCover[:] (this should be at the top of your function). It creates a slice (again: this link) containing the whole list, effectivly copying it.

• Using itertools.permutations wich does the thing you want to do. (see @John Coleman 's comment on your question) See the python documentation for more details.