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"];

CodePudding user response：

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"];

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".

CodePudding user response：

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);