Array equality: Issue with duplicates

Question

I've built my own ''array equality'' function and when all values in an array are unique it works as expected:

Example: (working)

var
   a = [1, 2, 3, ["a", "b"]],
   b = [1, 2, 3, ["a", "b"]];

arrayEquals(a, b); /* returns: [true, true, true, [true, true]] */

When there are duplicate values, however, the final result is damaged heavily:

Example: (non-working)

In this example, 1 exists twice in the first array. The problem is that the second 1 will return the first 1 of the second array as its match, even though that 1 has been already matched right a step ago by the previous 1 of the first array.

var
   a = [1, 1, 2],
   b = [1, 2, 2];

arrayEquals(a, b); /* returns: [true, false, false] */
                   /* should return: [true, false, true] */

Question:

Is there a way to safely remove or avoid checking the elements that were matched so that the result is altered?

---

What I've tried:

1) I have tried removing the elements that are found to exist in both arrays in the way that follows, but unfortunately it doesn't do any good:

Example:

if (eachA === eachB) {
   a.splice.call(index, 1); // Removing the matched elements
   b.splice.call(jindex, 1);  // Removing the matched elements
   result[index] = true;
}

2) I've tried if (eachA === eachB && !result[index] && !result[jindex]) result[index] = true; as well thinking that, if result[index] and result[jindex] are already true, it means that a value in one array has been matched to a value in the other.

---

Code:

/* Main function */
function arrayEquals(a, b, result) {
  return (a === b && a !== null) || (a.length === b.length &&
    (function check(a, b, result) {
      /* Check equality between 'a' and 'b' arrays */
      a.forEach(function(eachA, index) {
        b.forEach(function(eachB, jindex) {
          if (eachA === eachB) result[index] = true;
          /* Handle objects */
          else if (isObject(eachA) && isObject(eachB))
            result[index] = objectEquals(a, b);
          /* Handle arrays */
          else if (isArray(eachA) && isArray(eachB))
            check(eachA, eachB, (result[index] = []));
          /* Turn all 'undefined' to 'false' */
          else result[index] = (!!result[index]) ? true : false;
        });
      });
      return result;
    })(a, b, (result = [])));
}

/* Usage */
var
  a = [1, 1, 2, ["a", "b"]],
  b = [1, 2, 2, ["a", "b"]];

console.log(arrayEquals(a, b)); /* returns: [true, true, true, [true, true]] */
                                /* should return: [true, false, true, [true, true]] */

/* Supplementary functions */
function isArray(array) {return !!array && array.constructor === Array;}

function isObject(object) {return !!object && object.constructor === Object;}

---

Checking Procedure:

var
   a = [1, 1, 2],
   b = [1, 2, 2];

• For every index of the first array, we check all indices of the second array to one-by-one find a match.

• For the first array, 1 (at index 0) matches 1 (at index 0) of the second array.

• Then for the first array, 1 (at index 1) doesn't match any of the indices of the second array (1 at index 0 doesn't count, because we found a match earlier).

• Lastly, for the first array, 2 (at index 2) matches 2 (at index 1) of the second array. RESULT: [true, false, true] | not equal.

Summary:

• Each index must have a match, maybe the same index or some other.

• If one index of the second array is used as a match for a previous index of the first array, it cannot be used as a match again.

• The same element must exist again at another index to be used.

Image:

Answer 1

I'm doing C# and C++, not JavaScript, so I can't give you working code. But here's some pieces of pseudecode that should give you an idea of how it could work.
This is written as it comes out of my mind, typed on a mobile phone (terrible job) and untested. Hope it works for you! Please apologize any misspelling, which is likely causes by german auto-correction.

bool Compare (array a, array b, ref array result)
{
  Check whether arrays existiert and length is equal, return false if not;

  array<bool> b_used = new array(length (b));
  for (int indexa = 0 to length(a)-1)
  {
    if (a is value or object)
    { // compare against every b
      result[indexa] = false;
      for (int indexb = 0 to length(b)-1)
      {
        if (b_used[indexb])
          continue;  // this is the key: don't use an index twice!

        if (a[indexa] == b[indexb])
        {
          result[indexa] = true;
          b_used[indexb] = true;
          break;
        }
      }
    }
    Else if (array)
    ...
    And so on.

Notice that inner arrays are treated separately and not compared with values from outer arrays.

Answer 2

If guaranteed your arrays are in the same structure you may do as follows;

var a = [1, 1, 2, ["a", "b"]],
    b = [1, 2, 2, ["a", "b"]];

function arrayCompare(a,b){
 return a.map((e,i) => Array.isArray(e) ? arrayCompare(e, b[i])
                                        : e === b[i]);
}

console.log(arrayCompare(a,b))

Answer 3

Perhaps, there are better ways than the following, but the following still gets the job done.

What the solution does:

Basically, what the following does is to change the values of eachA and eachB, if they are equal, to some Regular Expression.

To my knowledge, two regular expressions can't be equal, so in the wild scenario that the same regexp already exists in one of the arrays, it would result in false no matter what.

After all who puts a RegExp in an array and happens to want to check if that array is equal to another?!

Solution:

if (eachA === eachB) {
   result[index] = true;
   a[index] = b[jindex] = /RegExp/;
}

In addition:

In order to avoid any surprises, the inner forEach loop must be broken so that the when a match is found, it goes straight to the next character. So, we change the forEch**to a **for and we break it.

if (eachA === eachB) {
   result[index] = true;
   a[index] = b[jindex] = /RegExp/;
   break;
}

Code:

/* Main function */
function arrayEquals(a, b, result) {
  return (a === b && a !== null) || (a.length === b.length &&
    (function check(a, b, result) {
      /* Check equality between 'a' and 'b' arrays */
      a.forEach(function(eachA, index) {
        for (var jindex = 0, eachB = b[jindex]; jindex < b.length;
             jindex++, eachB = b[jindex]) {
          if (eachA === eachB) result[index] = true,
            a[index] = b[jindex] = /RegExp/, break;
          }
          /* Handle objects */
          else if (isObject(eachA) && isObject(eachB))
            result[index] = objectEquals(a, b);
          /* Handle arrays */
          else if (isArray(eachA) && isArray(eachB))
            check(eachA, eachB, (result[index] = []));
          /* Turn all 'undefined' to 'false' */
          else result[index] = (!!result[index]) ? true : false;
        }
      });
      return result;
    })(a, b, (result = [])));
}

/* Usage */
var
  a = [1, 2, 2, ["a", "b"]],
  b = [1, 2, 2, ["a", "b"]];

console.log(JSON.stringify(arrayEquals(a, b)));

/* Supplementary functions */
function isArray(array) {return !!array && array.constructor === Array;}

function isObject(object) {return !!object && object.constructor === Object;}

Answer 4

Both arrays should have the same length and exactly the same elements in them in any order.

You can use Array.prototype.filter(), .length of returned array

var a = [1, 1, 2],
  b = [1, 2, 2],
  c = [1, 2, 1],
  d = [2, 1, 3],
  e = [2, 2, 1],
  f = [2, 1, 2];
    

var compare = (a, b) => 
      a.map(el =>
        b.filter(item => item === el).length ===
        a.filter(item => item === el).length
      );

console.log(compare(a, b), compare(c, d), compare(e, f))

Answer 5

Here is a fully recursive function that will compare the arrays:

function equality(array1, array2){
	if(array1.length === 0 ) return [];

	if(Array.isArray(array1[0]) && Array.isArray(array2[0])){
		return [equality(array1[0],array2[0])].concat(equality(array1.splice(1),array2.splice(1)));
	}
	return [array1[0] === array2[0]].concat(equality(array1.splice(1),array2.splice(1)));
}
console.log(equality([1,2,[3,3]], [1,2,[3,3]]));
console.log(equality([1,2,[3,2]], [1,2,[3,3]]));
console.log(equality([4,2,[3,3], 1], [1,3, 2,[3,3]]))

Answer 6

You are overcomplicating. You only need to map the longest array, and for each index compare if both elements (if any) are arrays. If they are, use recursion, otherwise compare normally.

function arrayCompare(arr1, arr2) {
  if(arr1.length < arr2.length) return arrayCompare(arr2, arr1);
  return arr1.map(function(item, idx) {
    if (idx >= arr2.length) return false;
    var b = Array.isArray(item) && Array.isArray(arr2[idx]);
    return (b ? arrayCompare : Object.is)(item, arr2[idx]);
  });
}
console.log(JSON.stringify(arrayCompare([1, 2, 3, ["a", "b"]], [1, 2, 3, ["a", "b"]])));
console.log(JSON.stringify(arrayCompare([1, 1, 2, ["a", "b"]], [1, 2, 2, ["a", "b"]])));
console.log(JSON.stringify(arrayCompare([1, 1, 2, 3], [1, 2, 2, ["a", "b"]])));
console.log(JSON.stringify(arrayCompare([1], [1, 2, 2, ["a", "b"]])));

Answer 7

This should work...

var
   a = [1, 2, 3, ["a", "b"]],
   b = [1, 2, 3, ["a", "b"]];

var
   c = [1, 1, 2, ["a", "b"]],
   d = [1, 2, 2, ["a", "b"]];

function arrayEquals(a, b) {
  if (a.length !== b.length) return false
  return a.map(function(el, i) {
    if (typeof a[i] === 'object' && a[i] instanceof Array) return arrayEquals(a[i], b[i])
    return a[i] === b[i] ? true : false
  })
}

console.log(arrayEquals(a, b))
console.log(arrayEquals(c, d))

Answer 8

Instead of two foreach loop use only one and compare with other element's same index. Please check below snippet.

/* Main function */
function arrayEquals(a, b, result) {
  return (a === b && a !== null) || (a.length === b.length &&
    (function check(a, b, result) {
      /* Check equality between 'a' and 'b' arrays */
      a.forEach(function(eachA, index) {
        if (eachA === b[index]) result[index] = true;
          /* Handle objects */
          else if (isObject(eachA) && isObject(b[index]))
            result[index] = objectEquals(a, b);
          /* Handle arrays */
          else if (isArray(eachA) && isArray( b[index]))
            check(eachA,  b[index], (result[index] = []));
          /* Turn all 'undefined' to 'false' */
          else result[index] = (!!result[index]) ? true : false;
      });
      return result;
    })(a, b, (result = [])));
}

/* Usage */
var
  a = [1, 1, 2, ["a", "b"]],
  b = [1, 2, 2, ["a", "b"]];

console.log(arrayEquals(a, b)); /* returns: [true, true, true, [true, true]] */
                                /* should return: [true, false, true, [true, true]] */

/* Supplementary functions */
function isArray(array) {return !!array && array.constructor === Array;}

function isObject(object) {return !!object && object.constructor === Object;}