Rearrange a list of points to reach the shortest distance between them
Question: I have a list of 2D points for example:

    
    
    1,1 2,2 1,3 4,5 2,1
    

The distance between these points is known (using math.hypot for example.) I
want to sort the list so that there is a minimum distance between them. I'm OK
with any possible solution order, as long as the points are in the shortest
order.

What is the most pythonic way to achieve this?

I was considering working out the distance between any item and any other
item, and choosing the smallest each time, but this would be a slow algorithm
on the lists I am working on (1,000 items would not be unusual.)


Answer: The technical question you're asking is similar to "What is the [minimum
hamiltonian path](http://en.wikipedia.org/wiki/Hamiltonian_path) of a graph"
(your tuples are vertices, and the distance between them are the weight of the
edges). This problem can't be solved in polynomial time, so your dataset had
better be small. Since your graph is complete (all nodes are connected), the
minimum hamiltonian path problem may not completely apply.

In any case, the answer below uses brute force. It permutes all possible
paths, calculates the distance of each path, and then gets the minimum.

    
    
    import itertools as it
    import math
    
    def dist(x,y):
        return math.hypot(y[0]-x[0],y[1]-x[1])
    
    paths = [ p for p in it.permutations([(1,2),(2,3),(5,6),(3,4)]) ]
    path_distances = [ sum(map(lambda x: dist(x[0],x[1]),zip(p[:-1],p[1:]))) for p in paths ]
    min_index = argmin(path_distances)
    
    print paths[min_index], path_distances[min_index]
    

Output:

    
    
    ((1, 2), (2, 3), (3, 4), (5, 6)) 5.65685424949
    

Note that the reverse path is an equivalent minimum

