Finding out the least-change operation to re-order a JS array

Question

I have got two JavaScript arrays - original and reordered. Assume that both arrays have the same items and each item in the array is unique. The corresponding items in both arrays may or may not be in the same order.

The original items of my problem are JS objects, but for demonstration's sake, I will just use strings here. So for example:

var original = ["life", "is", "trying", "things", "to", "see", "if", "they", "work"];
var reordered = ["life", "they", "is", "trying", "to", "things", "work", "see", "if"];

So my task is to create a third array (let's call it extracts) containing the items that need to be taken out from original and reinsert back into the original in order to transform original in the order of reordered.

Using the above example, the worked-out extracts would probably be:

extracts = ["things", "they", "work"];

After extraction, original would become:

original = ["life", "is", "trying", "to", "see", "if"];

Using this extracts array, I can then reinsert each item into the original accordingly to form reordered

But the problem is: how can I programmatically work out the shortest extracts array possible for the task? In other words, how can I take out the least number of items from original to form the reordered?

---

Bonus It would be great if the items in extracts are sorted in the relative order of reordered. Using the above example, it would be:

extracts = ["they", "things", "work"];

Answer 1

function LCS(original, reordered) {
var m = original.length;
var n = reordered.length;
var L = new Array(m + 1);
var i, j;

for (i = 0; i <= m; i++) {
    L[i] = new Array(n + 1);
}

for (i = 0; i <= m; i++) {
    for (j = 0; j <= n; j++) {
        if (i === 0 || j === 0) {
            L[i][j] = 0;
        } else if (original[i - 1] === reordered[j - 1]) {
            L[i][j] = L[i - 1][j - 1] + 1;
        } else {
            L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);
        }
    }
}

var index = L[m][n];
var extracts = new Array(index);
i = m;
j = n;
while (i > 0 && j > 0) {
    if (original[i - 1] === reordered[j - 1]) {
        extracts[index - 1] = original[i - 1];
        i--;
        j--;
        index--;
    } else if (L[i - 1][j] > L[i][j - 1]) {
        i--;
    } else {
        j--;
    }
}
return extracts;

}

var original = ["life", "is", "trying", "things", "to", "see", "if", "they", "work"];
var reordered = ["life", "they", "is", "trying", "to", "things", "work", "see", "if"];
var extracts = LCS(original, reordered);
console.log(extracts); // ["things", "they", "work"]

Answer 2

Overview

This can be solved using an implementation of a Longest Increasing Subsequence algorithm, by thinking of the indices of the reordered items in the original list. This only works if, as the problem states, each item is different.

Here's one version:

// Utility functions
const range = (lo, hi) => Array .from ({length: hi - lo}, (_, i) => lo + i)

const maximum = (gt, init) => (xs) => 
  xs .reduce ((a, x, i) => i == 0 || gt (x, a) ? x : a, init)

const maxByLength = maximum ((a, b) => a .length > b .length, -Infinity)

const missing = (cs, ps) => cs .filter ((c) => !ps .includes (c))

// Implementation of longest increasing subsequence algorithm
const lis = (xs) => maxByLength (xs .reduce ((acc, x) => [
  ...acc,
  maxByLength (acc .filter ((a) => (a .at (-1) || -Infinity) < x)) .concat (x)
], [[]]))

// Main function
const itemsToMove = (original, reordered) => 
  missing (
    range (0, original .length), 
    lis (reordered .map (s => original .indexOf (s)))
  ) .map ((i) => original [i])
    .sort ((a, b) => reordered .indexOf (a) - reordered .indexOf (b))

// Demo
console .log (itemsToMove (
  ['life', 'is', 'trying', 'things', 'to', 'see', 'if', 'they', 'work'], 
  ['life', 'they', 'is', 'trying', 'to', 'things', 'work', 'see', 'if']
))

Explanations

We start with a few helper functions:

• range returns a range of integers between lo (inclusive) and hi (exclusive). For instance,

  range (3, 12) //=> [3, 4, 5, 6, 7, 8, 9, 10, 11]
  

• maximum takes a function which reports whether one value is less than another, plus an initial value, and returns a function which takes an array of values and returns the largest of them according to your function. For instance

  maximum ((a, b) => Math.abs (a) > Math.abs (b), -Infinity) ([-8, 6, 7, 5, -3, 0, -9]) //=> -9
  

• maxByLength takes an array of arrays and returns the longest one. For instance,

  maxByLength ([[8], [6, 7, 5], [3], [0, 9]]) //=> [6, 7, 5]
  

  We could have written this in many other ways, but maximum is a genuinely useful function, so it feels clean to write in terms of it.

• missing is central here. It takes two sorted lists of numbers: the targets and our test cases, and reports back which of our target numbers is not in the test cases. For instance,

  missing ([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 3, 4, 6, 7]) //=> [2, 5, 8, 9]
  

Our key function is lis which finds the longest subsequences of increasing values in a sequence of values. There are probably more efficient versions of this, but this one should be O (n^2), which I believe is the minimum achievable, so nothing is asymptotically faster beyond a constant factor. It works by progressing through the list of values, starting with just an empty array, and checking which ones could be extended with the current value to keep an increasing list, chooses the maximum-length one of those, and stores a new list which is that one concatenated with the current value. More detail is below.

Our main function is itemsToMove. This takes the original and reordered lists, find the indices of each reordered value in the original list, finds the longest increasing subsequence of these values, then calls missing passing the full list of indices (just 0, 1, ..., up to one less than our input length) and the extracted subsequence to find which indices are missing. Then we map over the resulting indices, looking up each in the original to get the actual missing values. Finally, we sort these according to their positions in the reordered array.

You say you have input objects and not strings. If your two arrays do not have shared references to these objects, you will need to change missing and reordered .map (s => original .indexOf (s)) to check for value equality rather than simple references.

Explanation of LIS

Testing these values to find the longest increasing subsequence, we test each number and find the longest increasing subsequence that ends on this number. We do this by filtering the subsequences we have so far, finding those where the last number is less than our target. Among these we choose the one with the shortest length (or the first of those if there's more than one), append our new number and store this.

When we've stored one for each number, we simply take the longest array among the results.

In this example:

/ [      10, 22, 9,  33, 21, 50, 41, 60, 80, 55                    ]
// [ [], 
//       [10], 
//           [10, 22], 
//               [9], 
//                   [10, 22, 33], 
//                       [10, 21], 
//                           [10, 22, 33, 50], 
//                               [10, 22, 33, 41], 
//                                   [10, 22, 33, 50, 60], 
//                                       [10, 22, 33, 50, 60, 80]
//                                           [10, 22, 33, 50, 55]  ]
//
// Longest: [10, 22, 33, 50, 60, 80]

When we hit 21, our existing items are [], [10], [10, 22], [9], and [10, 22, 33] We can add 21 to [], [10], and [9]. We choose the first of the longest ones ([10], and [9]), and append 21, giving us [10, 21] for this step.

And when we hit 50, our existing terms are now [], [10], [10, 22], [9], [10, 22, 33], and [10, 21]. We can append 50 to all of these, so we choose the first of the longest ones (just [10, 22, 33]) and append 50, giving us [10, 22, 33, 50] for this step.

And so on. At the end, we simply select the longest of the values we've found.

Answer 3

Compute the dynamic programming table for a longest common subsequence and then walk it to determine the reverse order in which words were deleted from reordered.

let original = ["life", "is", "trying", "things", "to", "see", "if", "they", "work"];
let reordered = ["life", "they", "is", "trying", "to", "things", "work", "see", "if"];
let table = [[0]];
for (let j = 0; j < reordered.length; ++j) {
  table[0].push(0);
}
for (let i = 0; i < original.length; ++i) {
  table.push([0]);
  for (let j = 0; j < reordered.length; ++j) {
    table[i + 1].push(
      original[i] == reordered[j]
        ? table[i][j] + 1
        : Math.max(table[i][j + 1], table[i + 1][j])
    );
  }
}
let extracts = [];
let i = original.length - 1;
let j = reordered.length - 1;
while (i >= 0 && j >= 0) {
  if (original[i] == reordered[j]) {
    --i;
    --j;
  } else if (table[i + 1][j + 1] == table[i][j + 1]) {
    --i;
  } else {
    extracts.push(reordered[j]);
    --j;
  }
}
while (j >= 0) {
  extracts.push(reordered[j]);
  --j;
}
extracts.reverse();
console.log(extracts);

Answer 4

Step 1

Algorithm

Create a false-order matrix, that for each pair of elements in the original-array that is out of order has a 1 and else it has a 0 at the respective index for the elements.

Example

For the trivial example mentioned in the comments this would be (I replaced the 0's with _ to make it easier to see the 1's):

original = ["C", "A"," B", "D"]
reordered = ["A", "B", "C", "D"]
false-order matrix:
_ 1 1 _
1 _ _ _
1 _ _ _
_ _ _ _

The matrix is always symmetric (out of order is by-directional) and the diagonal is 0 (an element is never out of order with itself). The 1's in the first row are

• [0, 1]: "C" is out of order with "A"
• [0, 2]: "C" is out of order with "B"

The rest of the pairs are already in the correct order e.g. [1, 2]: "A" with "B" etc.

Step 2

Algorithm

Find the least number of columns and rows, that you have to remove (extract the element) for the matrix to only have 0's left.

Example

For this example there is only one best solution, to remove the first element "C" (position 0). Else you would need to remove position 1 ("A") and position 2 ("B") which would need 2 extractions instead of 1.

Caveat

Problem

While creating the false-order matrix (step 1) should be trivial, finding the biggest subset of the false-order matrix that contains only zeros (step 2) is more tricky, but I'm sure, that there is a deterministic way to do exactly that.

Solution?

One thing to consider to create this algorithm is, that there is only exactly two ways to solve an unordered pair: you need to extract either of the two elements from that pair (remove either the row or the column of the cell from the matrix). So if you have a 1 where the rest of the column is 0 but the rest of the row is not only 0, then it is always best to remove the row as removing the column would only solve one unordered pair while removing the row does solve the same unordered pair and others too (so it is at least as good). For the example above the unordered pair "C" and "B" can be solved by extracting either "C" or "B", but it is best to remove "C" because that resolves the unordered pair "C" and "A" as well. This algorithm works in the trivial case if there's always a solo 1 in a row or column, but you unfortunately can't always count on that.

I think part of an algorithm that can deal with non-trivial cases could be iterative swapping of a pair of elements from the matrix (swapping both the columns and rows) to achieve a square of 0's in the top-left corner as big as possible. This square contains now the elements that you keep, and the others are the ones you extract. Of course you need to keep track of which original element each element is after all the swapping, but you can do that, by swapping the elements in a copy of the original-array in the same way that you swap the columns of your false-order matrix.

---

Second Example

Your example would be:

original = ["life", "is", "trying", "things", "to", "see", "if", "they", "work"]
reordered = ["life", "they", "is", "trying", "to", "things", "work", "see", "if"]
false-order matrix:
_ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ 1 _
_ _ _ _ _ _ _ 1 _
_ _ _ _ 1 _ _ 1 _
_ _ _ 1 _ _ _ 1 _
_ _ _ _ _ _ _ 1 1
_ _ _ _ _ _ _ 1 1
_ 1 1 1 1 1 1 _ _
_ _ _ _ _ 1 1 _ _

The two 1's you see in the middle are the positions 3 ("things") and 4 ("to") that are out of order relative to each other. Column and Row 7 is "they" which is out of order with a lot of elements ("is", "trying", "things", "to", "see" and "if"). The last column and row indicates "work" which is only out of order with "see" on position 5 and "if" on position 6.

For this example, you always remove the element 7 ("they") and the element 8 ("work"). But then you can decide between removing element 3 ("things" or element 4 ("to"), both work. So the two least extractions are:

extracts = ["things", "they", "work"];

or

extracts = ["to", "they", "work"];

The sorting-algorithm described above as possible solution could work like this in this example:

          X   Y   
  _ _ _ _ _ _ _ _ _
  _ _ _ _ _ _ _ 1 _
  _ _ _ _ _ _ _ 1 _
  _ _ _ _ 1 _ _ 1 _
X _ _ _ 1 _ _ _ 1 _
  _ _ _ _ _ _ _ 1 1
Y _ _ _ _ _ _ _ 1 1
  _ 1 1 1 1 1 1 _ _
  _ _ _ _ _ 1 1 _ _

You swap columns and rows X and Y, resulting in the following matrix which can't be reduced further:

  _ _ _ _ _ _ _ _ _
  _ _ _ _ _ _ _ 1 _
  _ _ _ _ _ _ _ 1 _
  _ _ _ _ _ _ 1 1 _
  _ _ _ _ _ _ _ 1 1
  _ _ _ _ _ _ _ 1 1
  _ _ _ 1 _ _ _ 1 _
  _ 1 1 1 1 1 1 _ _
  _ _ _ _ 1 1 _ _ _

So you have a 5x5-square in the top left corner and you need to extract the last three elements. You did all of the swapping on the original-array as well ("to" was swapped with "if") which results in:

["life", "is", "trying", "things", "if", "see", "to", "they", "work"]

The last 3 elements are the ones you need to extract: "to", "they" and "work".