<p>附加部分似乎微不足道;您可以通过<code>list2 + list1</code>或<code>list1 + list2</code>添加这两个列表,具体取决于您希望第一个元素是什么。困难的部分是分类,所以我将通过这篇文章来解决这个问题。为了简单起见,我还删除了字符串标识符,它是每个元组的第一个元素,并假设数据是以<code>Tuple[int, int]</code>的形式提供的</p>
<p>首先,我将创建一个helper函数来计算两个给定元组之间的距离。我不完全确定如何定义距离函数,所以在本例中我使用了<a href="https://en.wikipedia.org/wiki/Taxicab_geometry" rel="nofollow noreferrer">Manhattan distance</a>,但您可以很容易地将它调整到您选择的另一个度量中</p>
<pre class="lang-py prettyprint-override"><code>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])
</code></pre>
<p>接下来,我们可以构造一个<a href="https://en.wikipedia.org/wiki/Adjacency_matrix" rel="nofollow noreferrer">adjacency matrix</a>存储任意两个给定位置之间的所有距离信息</p>
<pre class="lang-py prettyprint-override"><code>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
</code></pre>
<p>现在,如果您对<code>locations[i]</code>和<code>locations[j]</code>之间的距离感到好奇,您可以简单地访问<code>matrix[i][j]</code>(或者等效地,<code>matrix[j][i]</code>,因为矩阵是对称的)</p>
<p>给定一些组合列表<code>locations</code>,我们现在可以循环遍历该列表,找出距离当前索引最远的城市,并将其附加到列表中以返回</p>
<pre class="lang-py prettyprint-override"><code>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
</code></pre>
<p><code>i</code>用作指针,我们在每次迭代中将<code>i</code>更改为“跳转”到不同的元素。一旦我们到达第<code>i</code>个位置,我们循环通过邻接矩阵的第<code>i</code>行,找到我们尚未访问过的地方中最远的位置,即尚未添加到排序的<code>result</code>列表中。一旦我们找到了最远的位置,我们将指针移动到该位置并继续循环,直到我们访问了所有位置</p>