这个问题出现在对象的数组(有序集(的同步中。
具体来说，考虑一个项目数组，同步到另一台计算机。 用户在我背后移动一个或多个对象，从而对数组重新排序。 当我的程序唤醒时，我看到新顺序，并且我知道旧顺序。 我必须将更改传输到另一台计算机，在那里复制新订单。 下面是一个示例：
index 0 1 2
old order A B C
new order C A B
将移动定义为将给定对象移动到给定的新索引。 问题在于通过在通信链路上传输最少数量的移动来表达重新排序，这样另一端就可以推断剩余的移动，方法是按旧顺序获取未移动的对象，并将它们移动到新顺序中尚未使用的索引中，从最低的索引开始并上升。 在大型阵列内移动少量对象从而取代大量对象的情况下，这种传输方法将非常有效。
坚持。 让我们继续这个例子。 我们有
CANDIDATE 1
Move A to index 1
Move B to index 2
Infer moving C to index 0 (the only place it can go)
请注意，需要传输前两个移动。 如果我们不将移动 B 传输到索引 2，B 将被推断为索引 0，我们最终会得到 B A C，这是错误的。 我们需要传递两个动作。 让我们看看我们是否可以做得更好...
CANDIDATE 2
Move C to index 0
Infer moving A to index 1 (the first available index)
Infer moving B to index 2 (the next available index)
在这种情况下，我们得到正确的答案，C A B，只传输一个动作，将 C 移动到索引 0。 因此，候选 2 优于候选 1。 还有四个候选人，但由于很明显至少需要一步才能做任何事情，我们现在可以停下来宣布候选人 2 是获胜者。
我想我可以通过暴力强行尝试所有可能的候选人来做到这一点，但对于 N 个项目的数组，有 N！(N 阶乘(可能的候选者，即使我足够聪明，可以像示例中那样截断不必要的搜索，在可能包含数百个对象的典型数组中，事情仍然可能变得非常昂贵。
仅传输整个订单的解决方案是不可接受的，因为为了兼容性，我需要模拟另一个程序的传输。
如果有人能写下答案，那就太好了，但建议去阅读计算机科学教科书XXX的N章是完全可以接受的。 我不知道这些书，因为我，嘿，只是一个电气工程师。
谢谢！
杰瑞·克里诺克
我认为这个问题可以简化为最长的公共子序列问题，只需找到这个公共子序列并传输不属于它的动作即可。没有最优的证明，只有我的直觉，所以我可能是错的。即使我错了，这可能是一些更花哨的算法的良好起点。
基于信息论的方法
首先，有一个位序列，使得 0 对应于"常规顺序"，11 对应于"不规则进入"。每当有不规则条目时，还要添加下一个条目的原始位置。
例如。对于以下情况，假定ABCDE的原始顺序
ABDEC： 001 3 01 2
BCDEA： 1 1 0001 0
现在，如果进行"移动"的概率是p，则此方法大约需要n + n*p*log(n(位。
请注意，如果 p 很小，则 0 的数量会很高。您可以将结果进一步压缩为：
n*(p*log(1/p