Алгоритм: оптимальный способ перестановки списка из одного заказа в другой?

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 содержат неупорядоченные и упорядоченные списки идентификаторов элементов. При переупорядочении списка самой дорогой операцией на самом деле является перемещение элементов 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' связаны для самой длинной увеличивающейся подпоследовательности. Лучшее, что вы можете сделать, это выбрать один из них и просто переместить другие элементы.

Answer 2

Разделение ключей и индексов массива на отдельный массив объектов {ключ, индекс}. Сортируйте этот массив (конечно, используя лучшую сортировку, которую вы можете; либо сортировку слиянием, если сравнения дороги, либо быструю сортировку, если они дешевые). Теперь вы знаете, из фактических индексов в отсортированный массив и значений индексов, хранящихся в каждом элементе, как переупорядочить исходный массив.

После того, как вы отсортировали ключи, «оптимальным» числом ходов будет O (n) исходного массива. Если вы хотите переставить исходный массив на месте, вы можете довольно просто вывести обмены из отсортированного списка индексов.

Answer 3

Knuth Volume 3 имеет раздел «Сортировка сетей». Он не вдавался в много подробностей о том, как построить минимальные сети сравнения, но приводит некоторые работы (например, Бэтчера и его самого) о том, как их построить. Обратите внимание, что хотя эти примечания являются «минимальными сетями сравнения», лишь немногие (если таковые имеются) действительно были доказанными минимальными - они пытаются минимизировать количество необходимых компараторов, но не обязательно успешный с точки зрения фактического достижения истинного минимума.

Answer 4

Сначала я подумал, что вы должны использовать Выбор сортировки вместо встроенного метода сортировки, поскольку он обеспечивает наименьшее количество необходимых свопов. Таким образом, вы можете просто перемещать элемент DOM при перемещении идентификатора в списке.