Génération de combinaisons uniques à partir d'un tableau imbriqué (JS)

Question

Je tente de générer des combinaisons uniques à partir d'un tableau de tableaux en Javascript.

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

Dans cet exemple, [3,1,1] est un double de [1,1,3]. Ajouter les nombres à un ensemble ne semble pas résoudre le problème des tableaux dupliqués, et hacher le tableau trié et stringifié semble être un hack.

Editer: recherche d'une solution n'impliquant pas de tableaux stringifiés, s'il existe.

Existe-t-il une meilleure façon de résoudre ce problème?

Answer 1

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

Vous pouvez trier les tableaux, de sorte qu'ils sont égaux, et d'utiliser une table de hachage pour rendre unique toute la chose.

Answer 2

Vous pouvez utiliser un ensemble avec un tableau à cordes trié et un filtre en conséquence.

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

Une approche légèrement différente sans tableaux de chaîne de caractères, mais avec une table de hachage imbriquées qui utilise la longueur comme première clé.

var array = [[1, 1, 3], [3, 1, 1], [4, 4, 4]], 
 
    unique = array.filter(function (hash) { 
 
     return function (a) { 
 
      var found = true; 
 
\t \t \t \t 
 
      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; }

Answer 3

tableaux de mappage des valeurs de hachage primitives permet d'identifier efficacement les doublons - dans vos permutations de cas.

Une fonction de hachage simple est donnée en triant le tableau et en le liant ou en le striant, que vous préférez éviter.

Pour les tableaux d'entiers avec une plage limitée, vous pouvez mapper chaque entier n sur le n-ème nombre premier. Le produit de ces facteurs premiers est votre hash. Étant donné qu'un produit peut être calculé en temps linéaire, c'est plus rapide que le tri au prix d'avoir à enregistrer un tableau peut-être grand nombre de nombres premiers:

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