In [1]:
#List of pairs from the exercise
pairs1 = [ (91, 102), (44, 55), (89, 90) , (56, 88), (102, 150) ] 
pairs2 = [ (34, 44), (45, 34), (22, 55), (88, 99), (102, 33) ]

Helper functions


In [2]:
"""
Euclidean distance:
  sqrt ( sum_i |xi - yi| )

However, for  sorting purposes, the sqrt root will not affect
the ordering as it is a monotonous function, so we can skip it
"""
def pair_distance(x,y):
    return (x[0] - y[0])**2 + (x[1] - y[1])**2

In [3]:
"""
Classical insertion sort algorithm

Includes a parameter key, which takes a function that will be applied 
to the values for the comparisons
"""

def insertion_sort(vec,key=lambda x:x):
    for i in range(len(vec)):
        j = i
        while j > 0 and (key(vec[j-1]) > key(vec[j])):
            tmp = vec[j-1]
            vec[j-1] = vec[j]
            vec[j] = tmp
            j -= 1
    return vec

Sorting strategy 1


In [4]:
"""
Sort the pairs, by defining the 'value' of the pair as the
Euclidean distance from the point to the origin (0,0)

Easily generalizable to use any distance measure
"""
def tuple_sort_1( pair_list ):
    #Create list of distances from each point to the origin
    sorted_list = insertion_sort(pair_list,key=lambda x:pair_distance(x,(0,0))) 
    return sorted_list

In [5]:
sorted_p1 = tuple_sort_1(pairs1)
sorted_p2 = tuple_sort_1(pairs2)

print "Sorted list {}".format(sorted_p1)
print "Corresponding distances from each point to origin {}".format(map(lambda x: pair_distance(x,(0,0)),sorted_p1))
print
print sorted_p2
print map(lambda x: pair_distance(x,(0,0)),sorted_p2)


Sorted list [(44, 55), (56, 88), (89, 90), (91, 102), (102, 150)]
Corresponding distances from each point to origin [4961, 10880, 16021, 18685, 32904]

[(34, 44), (45, 34), (22, 55), (102, 33), (88, 99)]
[3092, 3181, 3509, 11493, 17545]

Sorting strategy # 2


In [6]:
from itertools import permutations

def hamiltonian_path_len(pair_list):
    path_len = 0;
    for idx in range(len(pair_list)-1):
        path_len += pair_distance(pair_list[idx],pair_list[idx+1])
    return path_len

"""
Tuple sorting version 2

Define an ordering of the pairs as the order in which the points
would be followed in the shortest Hamiltonian path starting from
the origin (0,0) and passing through all points in the list

Possibly not best solution, as multiple solutions might exist. 
With no additional info, it is hard to know whether sortings could be
considered "equivalent", or whether only one unique solution should exist
"""
def tuple_sort_2(pair_list):
    shortest_path = None
    min_len = float('inf')
    # Try all (bruteforce) possible paths
    # Shortest hamiltonian path is NP complete
    # For n=5 is still solvable like this
    for possible_path in permutations(pair_list):
        #Calculate length of the hamiltonian path starting at the origin
        current_len =  hamiltonian_path_len( ((0,0),) + possible_path )
        #If current path is shorter than all the rest, keep as putative shortest
        if current_len < min_len:
            min_len = current_len
            shortest_path = possible_path

    return shortest_path, min_len

In [7]:
sorted2_p1 = tuple_sort_2(pairs1)
sorted2_p2 = tuple_sort_2(pairs2)

print "Sorted list 1 : {}  with distance {} ".format(*sorted2_p1)
print
print "Sorted list 2: {}  with distance {} ".format(*sorted2_p2)


Sorted list 1 : ((44, 55), (56, 88), (89, 90), (91, 102), (102, 150))  with distance 9860 

Sorted list 2: ((22, 55), (34, 44), (45, 34), (102, 33), (88, 99))  with distance 11797