排序二维列表python

Question

我有这样的二维列表

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

实际上这些是2D-Euclidean空间中的坐标.我希望按照关闭点顺序排列的方式对其进行排序.因此,列表如下所示

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

但它没有返回我所需的结果.非常感谢您的帮助.谢谢

Answer 1

我不确定这是一个排序问题; 它更像是一个分组(或优化？)

排序需要一些标准才能将[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

蛮力解决方案是尝试所有排列,并选择最小化此总和的排列.