How to get the differences between two arrays in JavaScript, including moved items

Question

I have two arrays, which represent two versions of the same array, and I would like to know the difference between them.

Unlike earlier questions, I would also like to know about items that merely moved. If an item is in both arrays, but it's in different places, I'd like to know about it. Additionally, I do not want items in the result diff that only moved because other items were added or removed, which of course causes all following items to change indices. I only consider items to have moved, if they changed their relative position to each other.

let old = [ "b", "c", "d", "e", "f", "g", "h", "i", "j" ];
let news = [ "a", "d", "c", "e", "f", "h", "i", "j" ];

// algo should result in
let added = [ "a" ];
let removed = [ "b", "g" ];
let moved = [ "d", "c" ];

Ideally, I would expect them to be treated the same as non-duplicated values. If an item is now added a second time, I would expected it to appear once in `added`. Ditto with removal. If there are unaltered duplicates at the start (e.g. "e" appears twice in old and new), they should not influence the calculation of the later items (e.g. "g"). — Ben Bucksch, Apr 04 '22 at 20:35
You might try some variant of [The Wagner-Fischer algorithm](https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm). You'd have to track actual additions/deletions/substitutions, not just their count. You would still need to calculate moves, but I think with the full list of additions and deletions, you should be able to remove them in pairs, calling these ones moves rather than addition/deletion pairs. — Scott Sauyet, Apr 04 '22 at 23:26

Ben Bucksch · Accepted Answer · 2021-10-09T01:47:01.163

2

let old = [ "b", "c", "d", "e", "f", "g", "h", "i", "j" ];
let news = [ "a", "d", "c", "e", "f", "h", "i", "j" ];

let added = news.filter(item => !old.includes(item));
let removed = old.filter(item => !news.includes(item));
// find items that only changed place
let oldCommon = old.filter(item => news.includes(item));
let newCommon = news.filter(item => old.includes(item));
let moved = newCommon.filter((item, i) => item != oldCommon[i]);

console.log("added", added);
console.log("removed", removed);
console.log("moved", moved);

edited Oct 09 '21 at 01:47

answered Oct 07 '21 at 00:10

Ben Bucksch

395
3
13

There's a bug in that algo: If there are duplicate items, it wrongly considers all following items as moved. – Ben Bucksch Oct 07 '21 at 01:11

score 0 · Answer 2 · edited Oct 09 '21 at 07:55

0

This solution also deals with duplicate problems.

let oldArray = [ "b", "c", "d", "e", "f", "g", "h", "i", "j" ];
let newArray = [ "a", "d", "c", "e", "f", "h", "i", "j" ];

let added = newArray.filter(function(item) {
  return oldArray.indexOf(item) === -1;
});
let removed = oldArray.filter(function(item) {
  return newArray.indexOf(item) === -1;
});
let moved = newArray.filter(function(item) {
  return oldArray.indexOf(item) !== -1 &&
    newArray.indexOf(item) !== -1 &&
    oldArray.indexOf(item) !== newArray.indexOf(item);
});
console.log(added);
console.log(removed);
console.log(moved);

edited Oct 09 '21 at 07:55

Ben Bucksch

395
3
13

answered Oct 07 '21 at 01:34

Satish Chandra Gupta

2,970
1
22
22

This shows h, i, j as moved, and therefore fails this requirement: "I do not want items in the result diff that only moved because other items were added or removed, which of course causes all following items to change indices. I only consider items to have moved, if they changed their relative position to each other." – Ben Bucksch Oct 09 '21 at 01:39

score 0 · Answer 3 · edited Apr 05 '22 at 10:50

The added and removed elements should be clear. For the moved elements we have to keep track of the indexes, based on the added and removed elements.

I loop over the newArray and if I find an added element I mark it's index with -1 and I'll continue the indexing where I left i.e.: [0, 1, -1, 2, 3]

In the case of the removed elements if I find a removed index then I'll increase the current and all of the following indexes i.e.: if the removed index is 5 then [0,1,2,3,4,5,6,7,8] becomes [0,1,2,3,4,6,7,8,9].

Finally I just loop over the newWithIndexes and compare the indexes (that I calculated) with the oldArrays indexes.

let oldArray = [ "b", "c", "d", "e", "f", "g", "h", "i", "j" ];
let newArray = [ "a", "d", "c", "e", "f", "h", "i", "j" ];

let added = newArray.filter(item => oldArray.indexOf(item) == -1);
let removed = oldArray.filter(item => newArray.indexOf(item) == -1);

var removedIndexes = [];
for (let removedItem of removed) {
  removedIndexes.push(oldArray.indexOf(removedItem));
}

let newWithIndexes = [];
var addedCount = 0;
let i = 0;
for (let item of newArray) {
  if (added.includes(item)) {
    newWithIndexes.push({el: item, index: -1});
    addedCount++;
  } else {
    newWithIndexes.push({el: item, index: i - addedCount});
  }
  i++;
}

var removedCount = 0;
for (let newWithIndex of newWithIndexes) {
  if (removedIndexes.includes(newWithIndex.index + removedCount)) {
    removedCount++;
  }

  if (newWithIndex.index != -1) {
    newWithIndex.index += removedCount;
  }
}

let moved = [];
for (let newWithIndex of newWithIndexes) {
  if (newWithIndex.index != oldArray.indexOf(newWithIndex.el)) {
    moved.push(newWithIndex.el);
  }
}

console.log(added);
console.log(removed);
console.log(moved);

@BenBucksch: While I think the code as you rewrote it is much nicer than what was originally supplied, I also think it's a step too far -- changing the poster's code not only to fix minor mistakes but to fit your preferences for style. — Scott Sauyet, Apr 05 '22 at 11:27
@ScottSauyet: Thanks. While I mostly only updated to ES6 syntax, I am fairly new at SO and don't know the customs yet of what is considered helpful. Duly noted, I'll consider that going forward. — Ben Bucksch, Apr 06 '22 at 14:02

How to get the differences between two arrays in JavaScript, including moved items

3 Answers3