Sorting list based on how far each tuple are-CodePudding

my_list1 = [['a', (7,1)], ['b', (20,7)], ['c', (0,0)], ['d', (7,0)]]
my_list2 = [['o', (12,6)]]

How do I order my_list1 so that when I append it to my_list2. It goes like this:

my_list2 = [['o', (12,6)], ['c', (0,0)], ['b', (20,7)],  ['d', (7,0)],  ['a', (7,1)]]

I am trying to combine both list but also sort the list based on how far each tuple is from each other. For example, the furthest tuple from (12,6) in my_list1 would be (0,0). The furthest tuple from (0,0) in my_list1, which hasn't be added to my_list2 would be (20,7).

I tried doing this:

my_list1 = [['a', (19,6)], ['b', (20,7)], ['c', (0,0)], ['d', (7,0)]]
my_list2 = [['o', (12,6)]]
difference =[]

for x,y in my_list1:
    difference.append((abs(my_list2[-1][1][0]- y[0]), abs(my_list2[-1][1][1]- y[1])))

but I realised I would have to sort this to find the furthest tuple, add it to my_list2, and then repeat all/ most steps again. Is there a better way of thinking of how to sort it? Sorry if it doesn't make sense, English is not my first language.

CodePudding user response：

I'm sure there's a more Pythonic way (probably using numpy) but here's a fairly straightforward way.

import math

my_list1 = [['a', (7,1)], ['b', (20,7)], ['c', (0,0)], ['d', (7,0)]]
my_list2 = [['o', (12,6)]]

# Return distance between 2 points
def distance(a, b):
    return math.sqrt((a[1][0]-b[1][0])**2   (a[1][1]-b[1][1])**2)

for i in range(len(my_list1)):
    # Make a new list of tuples
    d = [(index, distance(point, my_list2[-1])) for index,point in enumerate(my_list1)]
    # Get the tuple with greatest distance
    farthest = max(d, key=lambda x:x[1])[0]
    # Add to one list, delete from other
    my_list2.append(my_list1[farthest])
    del my_list1[farthest]

print(my_list2)

Output:

[['o', (12, 6)], ['c', (0, 0)], ['b', (20, 7)], ['d', (7, 0)], ['a', (7, 1)]]

CodePudding user response：

The appending part seems trivial; you can just add the two lists via list2 list1 or list1 list2 depending on what you want your first element to be. The difficult part is sorting, so I'll try to address that through this post. For simplicity, I've also removed the string identifier that is the first element of each tuple and assume that the data is provided in the form of Tuple[int, int].

First, I would create a helper function that calculates the distance between two given tuples. I'm not entirely sure how you want to define your distance function, so I went with the Manhattan distance in this case, but you could easily adapt it into another measurement of your choice.

def get_distance(x, y):
    # x and y are tuples of the form (int, int)
    return abs(x[0] - y[0])   abs(x[1] - y[1])

Next, we can construct an adjacency matrix that stores all the distance information between any two given locations.

def build_adjacency_matrix(locations):
    matrix = []
    num_locations = len(locations)
    for i in range(num_locations):
        row = []
        for j in range(num_locations):
            row.append(get_distance(locations[i], location[j])
        matrix.append(row)
    return matrix

Now, if you are curious about the distance between locations[i] and locations[j], you can simply access matrix[i][j] (or equivalently, matrix[j][i], since the matrix is symmetric).

Given some combined list locations, we can now loop through the list to find out the city that is farthest from the current index and append it to the list to return.

def sort_by_farthest(locations):
    result = []
    visited = set()
    matrix = get_adjacency_matrix(locations)
    i = 0
    while len(visited) < len(locations):
        result.append(locations[i])
        visited.add(i)
        farthest = -1
        distance = -1
        for j in range(len(locations)):
            if j not in visited:
                candidate_distance = matrix[i][j]
                if candidate_distance > distance:
                    farthest = j
                    distance = candidate_distance
        i = farthest
    return result

i serves as a pointer, and we change i at each iteration to "jump" to a different element. Once we are at the i-th location, we loop through the i-th row of the adjacency matrix to find the farthest location among the place we haven't visited yet, i.e., haven't added to the sorted result list yet. Once we have found the farthest location, we move the pointer to that position and continue through the loop, until we have visited all locations.