按相似性对行和列进行sorting的algorithm

我遇到了一个电子表格 ，它解释了对包含二进制数据的matrix的行和列进行sorting的方法，以便连续行和列之间的变化数量被最小化。

例如，从以下开始：

在经过扩展的标签中描述的15个手动步骤之后，获得下面的表格：

我想知道：

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

谢谢 ！

Answer 1

您可以用一个向量L = [1, 1, 0, ... 1]来表示每一行，然后通过在L0之间不同的对应位置上的元素的数量来定义两条线d(L0, L1)之间的距离和L1 。 这就是所谓的二进制汉明距离 。 如果你有非二进制数据，你只会扩展你的距离定义，是的，Levenshtein距离将是一个选项。

一旦你的距离定义良好，你的问题的其余部分是最小化连续行之间的距离。 这正是旅行推销员问题 ，这是已知的NP难（ http://www.diku.dk/hjemmesider/ansatte/jyrki/Paper/EKP85.pdf ）。

直接的解决scheme（访问所有排列）是O（n！），但是通过使用dynamic编程可以轻松完成，例如Held-Karp_algorithm 。 还有近似algorithm，如Nearest_neighbour_algorithm ，它可以快速计算非最优解。

最后，对于实现，你可以很容易地谷歌“旅游销售人员excel / python”，并find许多教程和例子。