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) ]
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
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)
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)