我不确定这是一个排序问题;它更多的是一种分组(或优化?)
排序需要一些标准才能将 [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]])
距离或radius极坐标中是平方和 (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]]
成对距离
In 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
order
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
显然,这具有更好的聚类效果,主要基于第二列值。
Your 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
一种强力解决方案是尝试所有排列,并选择使该总和最小化的排列。