算法：将列表从一个订单重新排列到另一个订单的最佳方法？ [英] Algorithm: optimal way to rearrange a list from one order to another?

问题描述

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

I'm not sure that my original question is clear enough. I need an algorithm that will compute the minimal sequence of moves to rearrange an array from one order to another. It is known that both arrays will contain the same elements (no duplicates) and have the same length. For example:

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

应返回类似于：

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

表示我应首先将元素d移动到b之后，然后将c移动到b之后，数组将按所需顺序移动。

which indicates that I should first move the element 'd' to after 'b', then move 'c' to after 'b' and the array will be in the desired order.

背景：我正在研究一个项目（移动 rtgui 到客户端，实际上）。现在我正在进行排序。基本上我有一个div列表，我想按任意顺序排序。我可以按如下方式获得所需的订单：

Background: I'm working on a project (moving most of the functionality in rtgui to the client-side, actually). Right now I'm working on sorting. Basically I have a list of divs that I want sorted in some arbitrary order. I can get the desired order as follows:

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元素。我这样做的原因如下：

Now hashes.before and hashes.after contain the unordered and ordered lists of element IDs. When reordering the list, the most expensive operation, by far, is actually moving the DOM elements around. I had been doing this as follows:

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

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

This works, but is slower than necessary, since on average, only 2 or 3 elements really need to be moved. Therefore, I need an algorithm that will compute the minimal sequence of moves to rearrange an array from one order to another (in this case, operating on hashes.before and hashes.after). Can anyone suggest one or give any ideas?

到目前为止，我尝试了几种通用的差异算法，但它们并没有真正给我我想要的东西。我认为我需要的是这样，但更专业。

I've tried several general-purpose "diff" algorithms so far, but they didn't really give me what I wanted. I think what I need is like that, but more specialized.

推荐答案

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

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

Find the longest increasing subsequence (according to the new sort order). Then move each element which is not in that sequence, into its place relative to the elements already in the sequence.

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

In your example, 'a, b, e' and 'a, c, e' are tied for longest increasing subsequence. The best you can do is choose one of those, and just move the other elements.

这篇关于算法：将列表从一个订单重新排列到另一个订单的最佳方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！