python - 如何将列表中具有公共(public)组件的向量放在一起？

Question

对向量列表(例如列表列表或具有整数的数组数组)进行排序，以使具有最多相邻整数的内部向量。每个组件只计数一次，并且只与一个数字配对。

一个例子。

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

对于许多事情来说，这是一种有用的算法，例如，将具有公共(public)组件(组件是整数索引)的时间任务放在一起。可能有人破案了？

Answer 1

这是 travelling salesman problem无需回到起始位置。为避免负指标，成本应表示为相邻列表之间不共有的元素数；这给你一个三角不等式，所以你可以使用度量 TSP 方法。

您可以自己实现一个 TSP 求解器，但使用现有的求解器可能更有意义；例如，Google 的 or-tools有 Python 绑定(bind)和示例代码，说明如何使用它们来解决 TSP 实例。