python - 按相似性对行和列进行排序的算法

Question

我跌倒了a spreadsheet这解释了一种对包含二进制数据的矩阵的行和列进行排序的方法，以便最小化连续行和列之间的更改次数。

例如，开始于:

在电子表格的选项卡中描述的 15 个手动步骤后，获得下表:

我想知道:

1. 这个算法或方法的通用名称是什么？
2. 如何将它应用到更大的表(其中 2^n 会溢出...)
3. 如何将其推广到非二进制数据，例如使用 Levenshtein 距离？
4. 如果有任何指向代码(Excel VBA、Python 等)的链接已经实现了这个(否则我会写它...)

谢谢!

Answer 1

可以用一个向量L = [1, 1, 0, ... 1]表示每一行，然后定义两行之间的距离d(L0, L1) 由 L0 和 L1 对应位置不同的元素个数。这被称为二进制 Hamming distance .如果您有非二进制数据，您只需扩展距离的定义，是的，Levenshtein 距离是一个选项。

一旦您明确定义了距离，剩下的问题就是最小化连续行之间的距离。这正是 Traveling salesman problem ，已知为 NP-hard(http://www.diku.dk/hjemmesider/ansatte/jyrki/Paper/EKP85.pdf)。

直接解决方案(访问所有排列)是 O(n!)，但您可以使用动态规划轻松地做得更好，例如 Held–Karp_algorithm .还有近似算法，比如Nearest_neighbour_algorithm快速计算出非最优解。

最后，对于实现，您可以轻松地在 google 上搜索“traveling salesman excel/python”并找到许多教程和示例。