算法：在给定的操作方法内，如何用最少的步数将一个列表排序成另外一个大小相同的列表。

[TJT]

起因

产品中有个用户排名列表（大小固定），于是有了个新的需求，这个列表要定时刷新，并且发生变化的用户高亮一下。 起初一看，不难嘛，位置变了就算发生变化了。但是有这种情况，有个用户突然插入到了列表的开头，那么对于剩下的用户来说，他们在列表中的位置都发生了变化，但这显然不符合常理，应该是只有刚插入的那个用户算是变化了，于是就展开了后面更复杂的情况。。。

可能的情况

旧列表 => 新列表 = {发生变化的下标集合}

1. [1, 2, 3, 4, 5] => [1, 2, 3, 4, 9] = {4}
2. [1, 2, 3, 4, 5] => [1, 2, 5, 4, 3] = {2, 4}
3. [1, 2, 3, 4, 5] => [0, 1, 2, 3, 4] = {0}
4. [1, 2, 3, 4, 5] => [3, 4, 5, 1, 2] = {3, 4}
5. [1, 2, 3, 4, 5] => [0, 1, 4, 3, 2] = {0, 2, 4}
6. [1, 2, 3, 4, 5] => [3, 1, 2, 4, 5] = {0}
   ...

方案 0

用排序算法，记录排序算法的对列表的所有修改，然后体现到界面上。在进一步优化可以针对数据特征来改进排序算法，但经过我们的讨论，这个方案很难接近最优解。

方案 1

定义以下操作

• Swap(a, b): Exchange location of a and b.
• Insert(x): Insert new item at index x, and delete last item.
• MoveSeq(startIndex, length, targetIndex): Move array at startIndex with length(min=1) to targetIndex.

最后问题就是：如何用最少的操作来将 A 列表变成 B 列表

首先考虑的是穷举，但最后发现不能用穷举来解决，因为没有边界来确定是否已经穷举完所有可能，并且目前的情况下，可能性是无限的。

然后想到用 GP( https://en.wikipedia.org/wiki/Genetic_programming) 来接近最优解，但这个实现难度也不小。

问题

1. 这个问题对应的是那个具体领域？ Permutation or Sort algorithm?
2. 有什么别的方法更简单粗暴？

最后

其实这个需求不是很重要，排名的变化是很有特征的，只要针对大部分出现的情况进行处理就好，就算没有处理到实际上也没什么影响。但这个问题本身我觉得是很有趣的，而且难度也不小，所以想看下大家对这个问题的解决思路，互相学习下~

先谢谢大家，第一次在 V2EX 发这么长的帖子，写的不好的地方请见谅。希望能看到脑洞大开的思路 XD

[slixurd]

Levenshtein distance?

[TJT]

@slixurd 谢谢！没有了解过这个，我研究下

[aheadlead]

看了几遍不是很明白
需要一些样例来说明

看标题立即就想到了 1#说的编辑距离
这是高中时的一道经典动态规划的题目

同建议看看 1#的内容

[aheadlead]

看了几遍不是很明白，需要一些样例来说明。看标题立即就想到了 1#说的编辑距离，这是高中时的一道经典动态规划的题目。同建议看看 1#的内容。

[TJT]

@aheadlead 嗯，谢谢，我已经试着用 Levenshtein distance 的算法来实现这个需求了。另外是 #可能的情况 里面的样例不够直观导致你不是很明白吗？

[Exin]

参考下 git diff 这种功能的思路？