MapSet to maintain unique array of arrays, Javascript - Stack Overflow

admin管理员组

文章数量:1292173

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

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.

• javascript
• arrays
• filter
• set
• unique

Share Improve this question Follow edited Jun 20, 2020 at 9:12 CommunityBot 111 silver badge asked May 4, 2017 at 1:14 RohitRohit 6,6031616 gold badges6464 silver badges9292 bronze badges 1

• 1 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. – adeneo Commented May 4, 2017 at 1:19

Add a comment  | 

6 Answers 6

Sorted by: Reset to default 38

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)

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

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}]

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

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

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

本文标签： MapSet to maintain unique array of arraysJavaScriptStack Overflow