算法:将列表从一个订单重新排列到另一个订单的最佳方法？

Question

编辑:我不确定我原来的问题是否足够明确.我需要一种算法来计算最小的移动顺序,以便将数组从一个顺序重新排列到另一个顺序.众所周知,两个数组都包含相同的元素(没有重复)并且具有相同的长度.例如:

reorder(
  ['d', 'a', 'c', 'b', 'e'],
  ['a', 'b', 'c', 'd', 'e']
)

应该返回类似的东西:

[
  {move:'d', after:'b'},
  {move:'c', after:'b'}
]

这表明我应该首先将元素'd'移动到'b'之后,然后将'c'移动到'b'之后,数组将按所需顺序移动.

---

背景:我正在研究一个项目(实际上将rtgui中的大部分功能转移到客户端).现在我正在进行排序.基本上我有一个div列表,我想按任意顺序排序.我可以按如下方式获得所需的订单:

var hashes = {
  before: [],
  after: [],
};
var els = $('div.interesting-class').toArray();
var len = els.length;

for(var i = 0; i < len; i++) hashes.before.push(els[i].id);
els.sort(getSortComparator());
for(var i = 0; i < len; i++) hashes.after.push(els[i].id);

现在hashes.before,hashes.after包含无序和有序的元素ID列表.重新排序列表时,到目前为止,最昂贵的操作实际上是移动DOM元素.我这样做的情况如下:

var c = $('#container-id');
$(els).each(function() {
  c.append(this);
});

这可行,但速度比必要慢,因为平均来说,实际上只需要移动2或3个元素.因此,我需要一种算法来计算最小的移动顺序,以便将数组从一个顺序重新排列到另一个顺序(在这种情况下,操作hashes.before和hashes.after).任何人都可以建议或提出任何想法吗？

到目前为止,我已经尝试了几种通用的"diff"算法,但它们并没有真正给我我想要的东西.我认为我需要的是这样,但更专业.

Answer 1

http://en.wikipedia.org/wiki/Longest_increasing_subsequence

找到增长最长的子序列(根据新的排序顺序).然后将不在该序列中的每个元素移动到相对于序列中已有元素的位置.

在您的示例中,'a,b,e'和'a,c,e'与最长的子序列相关联.你能做的最好就是选择其中一个,然后移动其他元素.