CODEWITHSUNDEEP
javascriptarraysalgorithmcombinations
colorbynumber
colorbynumber

Reputation: 21

Generating unique combinations from a nested array (JS)

I'm trying to generate unique combinations from an array of arrays in Javascript.

Input: [ [1,1,3], [3,1,1], [4,4,4] ]
Output: [ [1,1,3], [4,4,4] ]

In this example, [3,1,1] is a duplicate of [1,1,3]. Adding the numbers to a Set doesn't seem to resolve the issue of duplicate arrays, and hashing the sorted, stringified array seems like a hack.

Edit: looking for a solution not involving stringified arrays, if it exists.

Is there a better way to solve this?

Upvotes: 0

Views: 403

Answers (3)

le_m
le_m

Reputation: 20248

Mapping arrays to primitive hash values allows to efficiently identify duplicates - in your case permutations.

A simple hash function is given by sorting the array and joining or stringifying it, which you prefer to avoid.

For integer arrays with limited range, you could map each integer n to the n-th prime number. The product of those prime factors is your hash. Since a product can be computed in linear time, this is faster than sorting at the cost of having to store a possibly large array of primes:

const primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61];

function hash(numbers) {
  return numbers.reduce((prod, n) => prod * primes[n], 1);
}

function unique(arrays) {
  let set = new Set();
  return arrays.filter(numbers => {
    let h = hash(numbers);
    return !set.has(h) && set.add(h);
  });
}

console.log(unique([[1,1,3], [3,1,1], [4,4,4]]));

Upvotes: 1

Nina Scholz
Nina Scholz

Reputation: 386868

You could use a set with a sorted stringed array and filter accordingly.

var array = [[1, 1, 3], [3, 1, 1], [4, 4, 4]],
    unique = array.filter(
        (s => a => (p => !s.has(p) && s.add(p))(a.slice().sort((a, b) => a - b).join()))(new Set)
    );

console.log(unique);

A slightly different approach without stringified arrays, but with a nested hash table which uses the length as first key.

var array = [[1, 1, 3], [3, 1, 1], [4, 4, 4]],
    unique = array.filter(function (hash) {
        return function (a) {
            var found = true;
				
            a   .slice()
                .sort(function (a, b) { return a - b; })
                .reduce(function (r, k) {
                    found = found && r[k];
                    return r[k] = r[k] || {};
                }, hash[a.length] = hash[a.length] || {});
            return !found;
        };
    }(Object.create(null)));

console.log(unique);
.as-console-wrapper { max-height: 100% !important; top: 0; }

Upvotes: 1

Jonas Wilms
Jonas Wilms

Reputation: 138557

var output=Object.keys(input.reduce((obj,el)=>(obj[el.sort().join()]=true,obj),{})).map(arr=>arr.split().map(e=>+e));

You could sort the arrays, so that they are equal, and use a hash table to make the whole thing unique.

Upvotes: 0

Related Questions