基于每个元组的距离排序列表

Question

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

如何对我的_列表1进行排序，以便在我将其附加到我的_列表2时。事情是这样的：

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

我试图结合这两个列表，但也排序列表的基础上有多远，每个元组是彼此的。例如，my_list1中距离（12,6）最远的元组是（0,0）。距离my_list1中的（0,0）最远的元组是（20,7），该元组尚未添加到my_list2中

我试着这样做：

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

但我意识到我必须对其进行排序以找到最远的元组，将其添加到我的_列表2中，然后再次重复所有/大部分步骤。有没有更好的方法来考虑如何排序？ 对不起，如果说不通的话，英语不是我的第一语言

Answer 1

我确信有一种更具python风格的方法（可能使用numpy），但这里有一种相当简单的方法

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)

输出：

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

Answer 2

附加部分似乎微不足道；您可以通过list2 + list1或list1 + list2添加这两个列表，具体取决于您希望第一个元素是什么。困难的部分是分类，所以我将通过这篇文章来解决这个问题。为了简单起见，我还删除了字符串标识符，它是每个元组的第一个元素，并假设数据是以Tuple[int, int]的形式提供的

首先，我将创建一个helper函数来计算两个给定元组之间的距离。我不完全确定如何定义距离函数，所以在本例中我使用了Manhattan distance，但您可以很容易地将它调整到您选择的另一个度量中

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

接下来，我们可以构造一个adjacency matrix存储任意两个给定位置之间的所有距离信息

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    

现在，如果您对locations[i]和locations[j]之间的距离感到好奇，您可以简单地访问matrix[i][j]（或者等效地，matrix[j][i]，因为矩阵是对称的）

给定一些组合列表locations，我们现在可以循环遍历该列表，找出距离当前索引最远的城市，并将其附加到列表中以返回

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用作指针，我们在每次迭代中将i更改为“跳转”到不同的元素。一旦我们到达第i个位置，我们循环通过邻接矩阵的第i行，找到我们尚未访问过的地方中最远的位置，即尚未添加到排序的result列表中。一旦我们找到了最远的位置，我们将指针移动到该位置并继续循环，直到我们访问了所有位置