Задача решена. 3 дня сидел, не думал, что такой тупой.
До конца прояснил в голове условия: необходимо преобразовать один массив в другой с минимальным количеством перестановок. Так же в конечном массиве могут присутствовать элементы, которых нет в начальном или, наоборот, какие-то отсутствовать. Алгоритм должен быть оптимизирован для ситуаций добавления/удаления/перестановки одного элемента.
Получилось вот что:
http://plnkr.co/edit/clW0aVqzaisUkUo44EOL?p=preview
Сложность от O(3n) до O(4n), т.е. линейная. Меньше всего операций удаления/вставки при отличии в одном элементе, больше всего — когда элементы идут в обратном порядке. Предполагалось, что элементы в массивах уникальны, хотя работает и с одинаковыми (тут особо не тестировал). Если кто-то подскажет вариант с еще меньшим количеством перестановок, будет здорово, но, думаю, меньше уже некуда.