javascript - Finding minimal distance between unsorted and sorted lists

Question

Let A be a list and S a sorted list of the same elements. Assume all elements are different. How do I find a minimal set of "moves" (move X before Y (or end)) that turns A into S?

Examples:

A = [8,1,2,3]
S = [1,2,3,8]

A => S requires one move: 
   move 8 before end

A = [9,1,2,3,0]
S = [0,1,2,3,9]

A => S requires two moves:
   move 9 before 0
   move 0 before 1

I prefer javascript or python, but any language will do.

Answer 1

This problem is equivalent to longest increasing subsequence problem.

You will have to define a comparison operator less. less(a, b) will return true if and only if a is before b in the target sequence. Now using this comparison operator, compute the maximum increasing sub sequence of the source sequence. You will have to move each element that is not part of this sub sequence (otherwise the sub sequence will not be maximum) and you can move it exactly once(moving it to its target position).

EDIT: As requested by amit here is my proof to the statement above: Lets we denote the target sequence B and lets denote the source sequence A. Let n = |A| and let k be the length of the longest increasing sequence as described above.

• Let's assume it is possible to reach B from A with less moves than n - k. This means that at least n - k + 1 elements from the A will not be moved. Let s₁,s₂,...s_m be the set of elements that are not moved. From the assumption we know that m > k. Now as these elements have not moved, than their relative position with respect to each other can not have changed. Thus the relative positions of all this elements in the target sequence B is the same as the one in A. Therefor the operator less(s_i, s_j) as defined above should be true for any i, j. But if this is true then s₁,s₂,...s_m is increasing sequence and as m > k this leads to a contradiction with the assumption that k is the length of the longest increasing sequence.
• Now lets show an algorithm to reach B from A by moving all elements but the ones that are part of the longest increasing sequence. We will move the elements in the order they appear in B. We will not move elements that are part of the longest increasing sequence. If the current element is the first one in B, we simply move it to the beginning of the sequence. Otherwise we move the current element right after the position of the previous element in B. Note that this element may either be the previous element we've moved or an element from the longest increasing sequence. Note that at each step when we are about to move element with index i, all elements with index 1, 2, ...i-1 will already be with correct relative positions with respect to each other.

EDIT: adding some code to make the answer clearer. I don't feel an expert in javascript so feel free to correct or criticize my solution.

Let's define a function transform(a, s) that takes two parameters - lists a and b as described in the statement. First I will create a map positions that maps each element in a to its position in s:

var positions = {};
for (var i = 0; i < a.length; ++i) {
  positions[a[i]] = i;
}

Now that I have this array I can define a helper function less as described in my answer above. Less will take two values a and b(and the helper map I just created) and return true if and only if a is before b in s(the target list):

function less(a, b, positions) {
  return positions[a] < positions[b];
}

Now I will not describe how can we find the maximum increasing subsequence in a with respect to that comparison operator. You can have a look at this question for detailed explanation how to do that. I will simply assume that I have a function defined:

function max_increasing_subsequence(a, positions)

That returns the maximum increasing subsequence in a with respect to the comparison operator less as defined above (using positions)as a list. I will use your second example to illustrate what we have so far:

A = [9,1,2,3,0]
S = [0,1,2,3,9]

The values in positions will be as follow:

positions = { 0 : 0,
              1 : 1,
              2 : 2,
              3 : 3,
              9 : 4}

And the result of max_increasing_subsequence(a, positions) will be [1, 2, 3]. By the way if there may be repeating elements in a it may be better to return indices instead of the elements from max_increasing_subsequence(in this particular example the difference will not be visible).

Now I will create another helper map to indicate which are the elements included in the maximum increasing subsequence:

var included = {};
l = max_increasing_subsequence(a, positions);
for (var i = 0; i < l.length; ++i) {
  included[l[i]] = true;
}

Now you can finish up the solution with a single iteration over s. I will add a special case for the last element to make code easier to understand:

if (!(s[s.length - 1] in included)) {
  console.log("Move" + s[s.length - 1] + " at the end");
}
for (var i = s.length - 2; i >= 0; --i) {
  if (!(s[i] in included)) {
    console.log("Move" + s[i] + " before " + s[i + 1]);
  }
}

Please note that in the solution above I assume that each time you log a new command, you log it with respect to the ordering of the array a right after all previous commands have been executed.

So in total I believe transform should look something like this:

function transform(a, s) {
  var positions = {};
  for (var i = 0; i < a.length; ++i) {
    positions[a[i]] = i;
  }
  var included = {};
  l = max_increasing_subsequence(a, positions);
  var included = {};
  for (var i = 0; i < l.length; ++i) {
    included[l[i]] = true;
  }
  if (!(s[s.length - 1] in included)) {
    console.log("Move" + s[s.length - 1] + " at the end");
  }
  for (var i = s.length - 2; i >= 0; --i) { // note s.length - 2 - don't process last element
    if (!(s[i] in included)) {
      console.log("Move" + s[i] + " before " + s[i + 1]);
    }
  }
}

I hope this code makes my answer more clear.