Cleaner method for finding the shortest distance between points in a python list?
Question: I have a list of tuples and an individual point in python e.g. [(1,2) , (2,5),
(6,7), (9,3)] and (2,1) , and I want to figure out the fastest path possible
created by all combinations of the individual point to the list of
points.(Basically I want to find the most efficient way to get to all of the
points starting from (2,1)). I have a manhattanDistance function that can take
it 2 points and output the distance. However, my algorithm is giving me
inconsistent answers (The heuristic is off for some reason)

What would be the correct way to accomplish this?

Here is my previous algorithm:

    
    
    def bestPath(currentPoint,goalList):
        sum = 0
        bestList = []
        while len(goallist) > 0:
            for point in list:
                bestList.append((manhattanD(point,currentPoint),point))
            bestTup = min(bestList)
            bestList = []
            dist = bestTup[0]
            newP = bestTup[1]
            currentPoint = newP
            sum += dist
    return sum
    


Answer: Since you don't have so many point, you can easily use a solution that try
every possibility.

Here is what you can do:

First get all combinations:

    
    
    >>> list_of_points = [(1,2) , (2,5), (6,7), (9,3)]
    >>> list(itertools.permutations(list_of_points))
    [((1, 2), (2, 5), (6, 7), (9, 3)),
    ((1, 2), (2, 5), (9, 3), (6, 7)),
    ((1, 2), (6, 7), (2, 5), (9, 3)),
    ((1, 2), (6, 7), (9, 3), (2, 5)),
    ((1, 2), (9, 3), (2, 5), (6, 7)),
    ((1, 2), (9, 3), (6, 7), (2, 5)),
    ((2, 5), (1, 2), (6, 7), (9, 3)),
    ((2, 5), (1, 2), (9, 3), (6, 7)),
    ((2, 5), (6, 7), (1, 2), (9, 3)),
    ((2, 5), (6, 7), (9, 3), (1, 2)),
    ((2, 5), (9, 3), (1, 2), (6, 7)),
    ((2, 5), (9, 3), (6, 7), (1, 2)),
    ((6, 7), (1, 2), (2, 5), (9, 3)),
    ((6, 7), (1, 2), (9, 3), (2, 5)),
    ((6, 7), (2, 5), (1, 2), (9, 3)),
    ((6, 7), (2, 5), (9, 3), (1, 2)),
    ((6, 7), (9, 3), (1, 2), (2, 5)),
    ((6, 7), (9, 3), (2, 5), (1, 2)),
    ((9, 3), (1, 2), (2, 5), (6, 7)),
    ((9, 3), (1, 2), (6, 7), (2, 5)),
    ((9, 3), (2, 5), (1, 2), (6, 7)),
    ((9, 3), (2, 5), (6, 7), (1, 2)),
    ((9, 3), (6, 7), (1, 2), (2, 5)),
    ((9, 3), (6, 7), (2, 5), (1, 2))]
    

Then create a function that give you the length of a combination:

    
    
    def combination_length(start_point, combination):
        lenght = 0
        previous = start_point  
        for elem in combination:
            lenght += manhattanDistance(previous, elem)
    
        return length
    

Finally a function that test every possibility:

    
    
    def get_shortest_path(start_point, list_of_point):
        min = sys.maxint
        combination_min = None
        list_of_combinations = list(itertools.permutations(list_of_points))
        for combination in list_of_combination:
            length = combination_length(start_point, combination)
            if length < min:
                min = length
                combination_min = combination
    
        return combination_min
    

Then finally you can have:

    
    
    import sys, itertools
    
    def combination_length(start_point, combination):
        lenght = 0
        previous = start_point  
        for elem in combination:
            lenght += manhattanDistance(previous, elem)
    
        return length
    
    def get_shortest_path(start_point, list_of_point):
        min = sys.maxint
        combination_min = None
        list_of_combinations = list(itertools.permutations(list_of_points))
        for combination in list_of_combination:
            length = combination_length(start_point, combination)
            if length < min:
                min = length
                combination_min = combination
    
        return combination_min
    
    list_of_points = [(1,2) , (2,5), (6,7), (9,3)]
    print get_shortest_path((2,1), list_of_points)
    

