logo标签列表

Python中对二维列表进行排序

pythonpandasnumpy
3

我有一个像这样的二维列表

a = [[42, 206], [45, 40], [45, 205], [46, 41], [46, 205], [47, 40], [47, 202], [48, 40], [48, 202], [49, 38]]

实际上这些是二维欧几里得空间中的坐标。我希望将它们按照距离排序，使得靠近的点排在一起。因此，列表应该如下所示：

sorted_a = [[45,205],[42,206],[46,205],[47,202],[48,202],[45,40],[46,41],[47,40],[48,40],[49,38]]

我也使用过这种方法

sorted_a = sorted(a, key=lambda x: (x[0],x[1]))

但是它没有返回我所需的结果。感谢您的帮助。谢谢。
2
最靠近原点的是什么？ - Willem Van Onsem
3
“sort it like in a way that close points come in a sequence” 的意思是“以让接近的点按顺序排列的方式进行排序”。 - Moinuddin Quadri
我是指最接近的点。实际上，我想做一些聚类，但我不想为此运行聚类分析。我有一个像这样的列表，我只想在给定阈值内平均最接近的点，这个阈值我可以自己决定。但目标是平均最接近的点。 - muazfaiz
1
@AzfarFaizan：但你不能基于两个元素之间定义的标准进行排序，因为那是一种偏序... - Willem Van Onsem
我已添加标签，以便更有经验的人能看到这个。 - hpaulj
1个回答
6

我不确定这是一个排序问题，更像是分组问题（或优化问题？）

排序需要一些标准来将[45,205]列表放在[42,206]之前。key适用于您可以想出一个数字来代表所需顺序的情况。

例如，计算距离原点的距离

A = np.array(a)创建一个numpy数组：

In [346]: A
Out[346]: 
array([[ 42, 206],
       [ 45,  40],
       [ 45, 205],
       [ 46,  41],
       [ 46, 205],
       [ 47,  40],
       [ 47, 202],
       [ 48,  40],
       [ 48, 202],
       [ 49,  38]])

极坐标下的距离或半径是平方和（不需要使用sqrt）。对此应用argsort可按照点到原点的距离对其进行排名。

In [347]: np.sum(A**2,axis=1)
Out[347]: array([44200,  3625, 44050,  3797, 44141,  3809, 43013,  3904, 43108,  3845])
In [348]: r = np.sum(A**2,axis=1)
In [349]: idx = np.argsort(r)
In [350]: idx
Out[350]: array([1, 3, 5, 9, 7, 6, 8, 2, 4, 0], dtype=int32)
In [351]: A[idx,:]
Out[351]: 
array([[ 45,  40],
       [ 46,  41],
       [ 47,  40],
       [ 49,  38],
       [ 48,  40],
       [ 47, 202],
       [ 48, 202],
       [ 45, 205],
       [ 46, 205],
       [ 42, 206]])

列表等效操作使用类似于键函数的方式。
def foo(xy):
    x,y=xy
    return x**2+y**2
In [356]: sorted(a, key=foo)
Out[356]: 
[[45, 40],
 [46, 41],
 [47, 40],
 [49, 38],
 [48, 40],
 [47, 202],
 [48, 202],
 [45, 205],
 [46, 205],
 [42, 206]]

成对距离

在numpy中，很容易计算出成对距离（使用其中一个scipy工具更加容易）。但是，你会用这些做什么呢？如何根据这些距离定义顺序呢？

例如，要使用我们经常被要求“向量化”的迭代方式：

In [369]: D = np.zeros((10,10))
In [370]: for i in range(10):
     ...:     for j in range(i,10):
     ...:         D[i,j] = np.sqrt(sum((A[i,:]-A[j,:])**2))
                  # D[i,j] = np.linalg.norm(A[i,:]-A[j,:])

In [372]: D.astype(int)
Out[372]: 
array([[  0, 166,   3, 165,   4, 166,   6, 166,   7, 168],
       [  0,   0, 165,   1, 165,   2, 162,   3, 162,   4],
       [  0,   0,   0, 164,   1, 165,   3, 165,   4, 167],
       [  0,   0,   0,   0, 164,   1, 161,   2, 161,   4],
       [  0,   0,   0,   0,   0, 165,   3, 165,   3, 167],
       [  0,   0,   0,   0,   0,   0, 162,   1, 162,   2],
       [  0,   0,   0,   0,   0,   0,   0, 162,   1, 164],
       [  0,   0,   0,   0,   0,   0,   0,   0, 162,   2],
       [  0,   0,   0,   0,   0,   0,   0,   0,   0, 164],
       [  0,   0,   0,   0,   0,   0,   0,   0,   0,   0]])

这是一个距离矩阵，为了显示方便而四舍五入。

numpy有一个词汇排序。我们可以使用它来先按第二个坐标排序，然后再按第一个坐标排序。这将使所有的200都聚在一起：

In [375]: np.lexsort(A.T)
Out[375]: array([9, 1, 5, 7, 3, 6, 8, 2, 4, 0], dtype=int32)
In [376]: A[_,:]
Out[376]: 
array([[ 49,  38],
       [ 45,  40],
       [ 47,  40],
       [ 48,  40],
       [ 46,  41],
       [ 47, 202],
       [ 48, 202],
       [ 45, 205],
       [ 46, 205],
       [ 42, 206]])

排过序的数组的成对距离如下：
array([[  0,   4,   2,   2,   4, 164, 164, 167, 167, 168],
       [  0,   0,   2,   3,   1, 162, 162, 165, 165, 166],
       [  0,   0,   0,   1,   1, 162, 162, 165, 165, 166],
       [  0,   0,   0,   0,   2, 162, 162, 165, 165, 166],
       [  0,   0,   0,   0,   0, 161, 161, 164, 164, 165],
       [  0,   0,   0,   0,   0,   0,   1,   3,   3,   6],
       [  0,   0,   0,   0,   0,   0,   0,   4,   3,   7],
       [  0,   0,   0,   0,   0,   0,   0,   0,   1,   3],
       [  0,   0,   0,   0,   0,   0,   0,   0,   0,   4],
       [  0,   0,   0,   0,   0,   0,   0,   0,   0,   0]])

搜索排列

另一种思考这个问题的方式是将其视为一个搜索问题，例如寻找最小化“旅行”距离（即连续点之间距离的总和）的点序顺序。

使用原始的a (A)，默认情况下使用np.linalg.norm方法计算连续点之间的距离为

In [407]: np.linalg.norm(A[1:]-A[:-1],axis=1)
Out[407]: 
array([ 166.02710622,  165.        ,  164.00304875,  164.        ,
        165.00303028,  162.        ,  162.00308639,  162.        ,
        164.00304875])

以及它们的总和：

In [408]: _.sum()
Out[408]: 1474.0393203904973

使用lexsort排序
In [410]: np.linalg.norm(A1[1:]-A1[:-1],axis=1)
Out[410]: 
array([   4.47213595,    2.        ,    1.        ,    2.23606798,
        161.00310556,    1.        ,    4.24264069,    1.        ,
          4.12310563])
In [411]: _.sum()
Out[411]: 181.07705580534656

很明显，这个更好的聚类是基于第二列数值得出的。

您的sorted_a稍微提高了这个总和：

In [414]: sortedA = np.array(sorted_a)
In [415]: np.linalg.norm(sortedA[1:]-sortedA[:-1],axis=1)
Out[415]: 
array([   3.16227766,    4.12310563,    3.16227766,    1.        ,
        162.0277754 ,    1.41421356,    1.41421356,    1.        ,
          2.23606798])
In [416]: _.sum()
Out[416]: 179.53993144488973

一个暴力的解决方案是尝试所有排列，并选择使这个总和最小的那个。
感谢您的简短回答。 - muazfaiz
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接