Javascript arrays ab=ba

Question

If i have a multidimensional array like: [[a,b],[a,c],[b,a],[b,c],[c,a],[c,b]] how can i go through and remove repeats where [a,b] is the same as [b,a].

also, the array is actually massive, in the tens of thousands. A for loop would have to be done backwards because the array length will shrink on every iteration. Im not even sure that an each loop would work for this. I really am at a loss for just a concept on how to begin.

Also, i tried searching for this for about an hour, and i don't even know how to phrase it.

Answer 1

Based on my understanding that you want to remove from the parent array any children arrays which hold the same set of objects without regard for order, this should do it is some code:

function getId(obj) { // apparently these objects have identifiers
  return obj._id; // I'm testing with MongoDB documents
}
function arraysEqual(a, b) {
  if (a === b) { return true; }
  if (a == null || b == null) { return false; }
  if (a.length != b.length) { return false; }
  aIds = [];  bIds = [];
  for (var i = 0; i < a.length; i++) {
    aIds.push(getId(a[i])); bIds.push(getId(b[i]));
  }
  aIds.sort(); bIds.sort();
  for ( var i = 0; i < aIds.length; i++ ) {
    if(aIds[i] !== bIds[i]) { return false; }
  }
  return true;
}
function removeRepeats(list) {
  var i, j;
  for (i=0; i < list.length; i++) {
    for (j=i+1; j < list.length; j++) {
      if (arraysEqual(list[i], list[j])) {
        list.splice(j,1);
      }
    }
  }
}

The removeRepeats function goes through each element and compares it with every element that comes after it. The arraysEqual function simply returns true if the arrays are equal. The isEquivalent function should test object equivalence. As noted on that webpage, there are libraries that test object equivalence. If you are okay with adding those libraries, you can replace the isEquivalent function with _.isEqual.

Answer 2

I think I'm going to try a different approach to this problem. I also think it'll be quicker than some of the solutions proposed (though we'd need of course to test it and benchmark it).

First off, why don't we take advantage of the hash oriented nature of javascript arrays and objects? We could create an object containing the relations (in order to create a kind of a map) and store in a new array those relationships that hasn't been stored yet. With this approach there's no problem about objects either, we just request for an identifier or hash or whatever for every object. This identifier must make the relationship between them possible.

UPDATE

• The script now controls the possibility of repeated elements f.e [[a,b],[a,b]]
• The script now controls the possibility of elements with the same object repeated f.e [[a,a],[a,a][a,a]] would return [a,a]

The code:

var temp = {},
    massive_arr = [['a','b'],['a','c'],['a','d'], ['b','a'],['b','c'],['b','d'],['c','a'],['c','b'],['c','d']],
    final_arr = [],
    i = 0,
    id1,
    id2;
for( ; i < massive_arr.length; i++ ) {
    id0 = objectIdentifier(massive_arr[i][0]);// Identifier of first object
    id1 = objectIdentifier(massive_arr[i][1]);// Identifier of second object

    if(!temp[id0]) {// If the attribute doesn't exist in the temporary object, we create it.
        temp[id0] = {};
        temp[id0][id1] = 1;
    } else {// if it exists, we add the new key.
        temp[id0][id1] = 1;
    }

    if( id0 === id1 && !temp[id0][id1+"_bis"] ) {// Especial case [a,a]
        temp[id0][id1+"_bis"] = 1;
        final_arr.push(massive_arr[i]);
        continue;// Jump to next iteration
    }

    if (!temp[id1]) {// Store element and mark it as stored.
      temp[id1] = {};
      temp[id1][id0] = 1;
      final_arr.push(massive_arr[i]);
      continue;// Jump to next iteration
    }

    if (!temp[id1][id0]) {// Store element and mark it as stored.
      temp[id1][id0] = 1;
      final_arr.push(massive_arr[i]);
    }
}
console.log(final_arr);

function objectIdentifier(obj) {
    return obj;// You must return a valid identifier for the object. For instance, obj.id or obj.hashMap... whatever that identifies it unequivocally.
}

You can test it here

SECOND UPDATE

Though this is not what was requested in the first place, I've changed the method a bit to adapt it to elements of n length (n can vary if desired).

This method is slower due to the fact that relies on sort to generate a valid key for the map. Even so, I think it's fast enough.

var temp = {},
massive_arr = [
    ['a', 'a', 'a'], //0
    ['a', 'a', 'b'], //1
    ['a', 'b', 'a'],
    ['a', 'a', 'b'],
    ['a', 'c', 'b'], //2
    ['a', 'c', 'd'], //3
    ['b', 'b', 'c'], //4
    ['b', 'b', 'b'], //5
    ['b', 'b', 'b'],
    ['b', 'c', 'b'],
    ['b', 'c', 'd'], //6
    ['b', 'd', 'a'], //7
    ['c', 'd', 'b'],
    ['c', 'a', 'c'], //8
    ['c', 'c', 'a'],
    ['c', 'd', 'a', 'j'], // 9
    ['c', 'd', 'a', 'j', 'k'], // 10
    ['c', 'd', 'a', 'o'], //11
    ['c', 'd', 'a']
],
    final_arr = [],
    i = 0,
    j,
    ord,
    key;
for (; i < massive_arr.length; i++) {
    ord = [];
    for (j = 0; j < massive_arr[i].length; j++) {
        ord.push(objectIdentifier(massive_arr[i][j]));
    }

    ord.sort();
    key = ord.toString();

    if (!temp[key]) {
        temp[key] = 1;
        final_arr.push(massive_arr[i]);
    }
}

console.log(final_arr);

function objectIdentifier(obj) {
    return obj;
}

It can be tested here

Answer 3

*** 
* Turns out the OP has objects in his list, so this approach won't
* work in that case. I'll leave this for future reference.
***

var foo = [['a','b'],['a','c'],['b','a'],['b','c'],['c','a'],['c','b']];

function removeRepeats(list) {
    var i;
    var b = [];
    var _c = [];

    for (i = 0; i < list.length; i++) {
        var a = list[i].sort();
        var stra = a.join("-");

        if(_c.indexOf(stra) === -1) {
            b.push(a);
            _c.push(stra);
        }
    }

    return b;
}

console.log(removeRepeats(foo));

It's not the most pretty code I've ever produced, but it should be enough to get you started I guess. What I'm doing is creating two new arrays, b and _c. b will be the array without the repeats. _c is a helper array which contains all the unique pairs already processed as a string, so I can do easy string comparisons while looping through list.