Map/Set to maintain unique array of arrays, Javascript

Question

I am trying to build unique array of arrays such that whenever I have new array to add it should only add if it doesn't already exist in collection

E.g. store all unique permutations of [1,1,2]

Actual : [[1,1,2],[1,2,1],[1,1,2],[1,2,1],[2,1,1],[2,1,1]]
Expected : [[1,1,2],[1,2,1],[2,1,1]]

Approaches I tried:

1. Array.Filter: Doesn't work because arrays are object and each value in uniqueArrComparer is a unique object reference to that array element.

function uniqueArrComparer(value, index, self) {
  return self.indexOf(value) === index;
}

result.filter(uniqueArrComparer)

2. Set/Map: Thought I can build a unique array set but it doesn't work because Set internally uses strict equality comparer (===), which will consider each array in this case as unique.
   We cannot customize object equality for JavaScript Set

3. Store each array element as a string in a Set/Map/Array and build an array of unique strings. In the end build array of array using array of unique string. This approach will work but doesn't look like efficient solution.

Working solution using Set

let result = new Set();

// Store [1,1,2] as "1,1,2"
result.add(permutation.toString());

return Array.from(result)
  .map(function(permutationStr) {

    return permutationStr
      .split(",")
      .map(function(value) {

        return parseInt(value, 10);
      });
  });

This problem is more of a learning exercise than any application problem.

Crandell

As you've gathered, there's no built-ins that will work with this particular setup where arrays inside an array need to be checked, not just the values, but the order as well. You'd have to roll your own, and that would mean either stringifying the arrays and checking the strings, or just checking each array individually agains the new array. – Bookstall

Answer 1

One way would be to convert the arrays to JSON strings, then use a Set to get unique values, and convert back again

var arr = [
  [1, 1, 2],
  [1, 2, 1],
  [1, 1, 2],
  [1, 2, 1],
  [2, 1, 1],
  [2, 1, 1]
];

let set  = new Set(arr.map(JSON.stringify));
let arr2 = Array.from(set).map(JSON.parse);

console.log(arr2)

Bookstall

Answer 2

The fastest method I've found is:

const points = [
  [0,0],
  [100,100],
  [400,400],
  [200,200],
  [200,200],
  [200,200],
  [300,300],
  [400,400],
]

const uniquePoints = Array.from(
  new Map(points.map((p) => [p.join(), p])).values()
)

All of the methods in this thread are fast. This one is faster than the Set method, however, as we never need to convert the stringified array back into a array.

To find unique objects, replace p.join() with JSON.stringify(p).

Note

In my case, the method shown above turned out to be the wrong strategy, as I was only really needing to check against identical adjacent points. For example, the test array used above includes the value [400,400] two times, though these values are not consecutive. The method shown above would have removed the second instance, while the code below would have kept it.

points = points.filter(
    (point, i) =>
      i === 0 ||
      !(points[i - 1][0] === point[0] && points[i - 1][1] === point[1])
  )

Leprose

this solution worked for me to get unique arrays from an array of arrays. But as someone learning, could you explain how it works? thank you – Singley

Answer 3

If you are ok to use a library, try lodash uniqWith. This will recursively find groups of arrays OR objects with the comparator of your choice: equal in your case.

var arrayofarrays = [ [1,1,2], [1,2,1], [1,1,2], [1,2,1], [2,1,1], [2,1,1] ]

const uniqarray = _.uniqWith(arrayofarrays, _.isEqual);

console.log(uniqarray) //=> [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

Bonus: it works on array of objects too

var objects = [{ 'x': 1, 'y': {b:1} }, { 'x': 1, 'y': {b:1} }, 
               { 'x': 2, 'y': {b:1} }, { 'x': 1, 'y': 2 }     ];

const uniqarray = _.uniqWith(objects, _.isEqual);

console.log(uniqarray) 
// => [{x: 1, y: {b: 1}}, {x: 2, y: {b: 1}}, {x: 1, y: 2}]

Patentor

Answer 4

To get around the problem of each array being a unique object, you can stringify it so it's no longer unique, then map it back to an array later. This should do the trick:

var arr = [
  [1, 1, 2],
  [1, 2, 1],
  [1, 1, 2],
  [1, 2, 1],
  [2, 1, 1],
  [2, 1, 1]
];


var unique = arr.map(cur => JSON.stringify(cur))
  .filter(function(curr, index, self) {
    return self.indexOf(curr) == index;
  })
  .map(cur => JSON.parse(cur))

console.log(unique);

Edifice

Answer 5

You can subclass Set for more flexibility in storing objects by storing the result of calling JSON.stringify on added objects.

class ObjectSet extends Set{
  add(elem){
    return super.add(typeof elem === 'object' ? JSON.stringify(elem) : elem);
  }
  has(elem){
    return super.has(typeof elem === 'object' ? JSON.stringify(elem) : elem);
  }
}
let set = new ObjectSet([[1,1,2],[1,2,1],[1,1,2],[1,2,1],[2,1,1],[2,1,1]]);
console.log([...set]);
console.log([...set].map(JSON.parse));//get objects back

Jellicoe

Answer 6

This answer uses reduce and find to check each of the values in the arrays.

const arr = [
  [1, 1, 2],
  [1, 2, 1],
  [1, 1, 2],
  [1, 2, 1],
  [2, 1, 1],
  [2, 1, 1]
];

const result = arr.reduce((unique, a) =>
  (unique.find(el => el[0] === a[0] && el[1] === a[1] && el[2] === a[2]) ?
    unique : [...unique, a]), []);

console.log(result);

references:

• https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/find
• https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/reduce

Singley