对向量列表（例如，具有整数数字的列表或数组列表）进行排序，以使内部向量与大多数相邻的通用整数数字相邻。每个组件仅计数一次，仅与一个数字配对。
一个例子。
Input
[
[ 4, 6, 2, 2, 10 ],
[ 5, 20, 2, 7, 9 ], # 1 component is common with previous
[ 5, 4, 2, 10, 9 ], # 3 ...
[ 9, 6, 3, 3, 0 ], # 1 ...
[ 5, 7, 2, 9, 5 ], # 1 ...
[ 9, 3, 6, 7, 0 ] # 2 ...
]
Output (common match number was 1+3+1+1+2 and became 2+3+3+1+4).
[
[ 4, 6, 2, 2, 10 ],
[ 5, 4, 2, 10, 9 ], # 2 components are common with previous
[ 5, 20, 2, 7, 9 ], # 3 ...
[ 5, 7, 2, 9, 5 ], # 3 ...
[ 9, 6, 3, 3, 0 ], # 1
[ 9, 3, 6, 7, 0 ] # 4 ...
]
我当前的"排序排序"解决方案（Python）无法正常工作：
def _near_vectors( vectors_ ):
"""
Return value - changed order of indexes.
"""
vectors = copy( vectors_ )
# Sort each vector
for i in range( len( vectors ) ):
vectors[ i ] = sorted( vectors[ i ] )
# Save info about indexes
ind = [ ( i, vectors[ i ] ) for i in range( len( vectors ) ) ]
sort_info = sorted( ind, key = itemgetter( 1 ) )
return [ v[ 0 ] for v in sort_info ]
失败的示例：
Input:
[
[0, 1, 2, 3],
[0, 1, 2, 4],
[4, 5, 6],
[4, 5, 13],
[5, 8, 9, 17],
[5, 12, 13],
[7, 8, 9],
[7, 10, 11],
[7, 11, 14, 15],
[7, 14, 15, 16]
]
Output: the same list, that is incorrect. [5, 12, 13] must be just after [4, 5, 13].
这是许多事情的有用算法，例如，使用常见组件（组件是整数索引）将时间任务汇总在一起。可能有人解决了这个情况？
这是旅行推销员问题，而无需返回起始位置。为了避免使用负标准，成本应表示为相邻列表之间共同的元素数量；这给您带来了三角形的不等式，因此您可以使用公制的TSP方法。
您可以自己实现TSP求解器，但使用现有的解决方案可能更有意义。例如，Google的Or-Tool具有Python绑定和示例代码，以使用它们解决TSP实例。
其正确的算法：
# Sort each vector
for i in range( len( vectors ) ):
vectors[ i ] = sorted( vectors[ i ] )
# Output
[
[0, 1, 2, 3],
[0, 1, 2, 4],
[4, 5, 6],
[4, 5, 13],
[5, 8, 9, 17],
[5, 12, 13],
[7, 8, 9],
[7, 10, 11],
[7, 11, 14, 15],
[7, 14, 15, 16]
]
# Save info about indexes
ind = [ ( i, vectors[ i ] ) for i in range( len( vectors ) ) ]
# Output convert to list with tuples (index,list[i])
[(0, [0, 1, 2, 3]),
(1, [0, 1, 2, 4]),
(2, [4, 5, 6]),
(3, [4, 5, 13]),
(4, [5, 8, 9, 17]),
(5, [5, 12, 13]),
(6, [7, 8, 9]),
(7, [7, 10, 11]),
(8, [7, 11, 14, 15]),
(9, [7, 14, 15, 16])]
sort_info = sorted( ind, key = itemgetter( 1 ) )
# Output sort by list first by sorting the first elements on each list
# then the second ones etc. For example list [4, 5, 13] comes before
# [5, 8, 9, 17] because their first element is 4 < 5. Then
# [5, 8, 9, 17] comes before [5, 12, 13] because the second element
# is 8 < 12 etc.
[(0, [0, 1, 2, 3]),
(1, [0, 1, 2, 4]),
(2, [4, 5, 6]),
(3, [4, 5, 13]),
(4, [5, 8, 9, 17]),
(5, [5, 12, 13]),
(6, [7, 8, 9]),
(7, [7, 10, 11]),
(8, [7, 11, 14, 15]),
(9, [7, 14, 15, 16])
]
我当前功能_near_vectors()的结果可以通过改进。
想法：通过将每个元素移动到更有价值的位置的函数（部分改善结果），改善简单排序解决方案的结果（部分分类），将"真空"中的向量移动到正确的位置）。例如。它计算相邻组件的当前值，并检查它们是否可以移动到另一个位置（带有另一个相邻组件），并在新形成的组之间具有更有价值的链接。
def _match( v1, v2 ):
"""
The number of identical elements in v1 and v2 where v1 and v2 are lists.
"""
res = len(list((Counter(v1) & Counter(v2)).elements()))
return res
def _mind( vectors, vi, i ):
"Calculate value of position i for vector vi in vectors."
def pos(i):
return 0 <= i < len( vectors )
if isinstance(vi, int):
if pos(vi):
v = vectors[vi][ 1 ]
else:
return 0
else:
v = vi
if pos(i):
return _match( vectors[ i ][ 1 ], v )
else:
return 0
def _near_vectors2(vectors):
i = 0
for v in vectors:
max_val = 0
new_pos = None
for k in range(len(vectors)):
if k != i:
v = vectors[ i ][ 1 ] # current vector
# Calc. sum of links, move if links are improved
next_k = k + 1 if i < k else k - 1
cur_mind = _mind(vectors, v, k) + _mind(vectors, v, next_k) - _mind(vectors, k, next_k) - _mind(vectors, v, i + 1 ) - _mind(vectors, v, i - 1 ) + _mind(vectors, i - 1, i + 1)
if cur_mind > max_val:
max_val = cur_mind
new_pos = k
# move element
if new_pos is not None:
vectors.insert( new_pos, vectors.pop( i ) )
i += 1
return vectors
所以，要使它起作用，我们可以致电：
near_indexes = _near_vectors2( near_vectors( vects ) )
输出列表中的每个元素都由两个组件组成：更改的索引和源向量。
说话。没有配对解决方案，这些决定都没有正常工作。结果可能不是"绝对"的，而是大量排序。