Verifique se todos os elementos em um array estão em um segundo array

Eu tenho dois arrays e quero verificar se todos os elementos em arr2 estão em arr1 . Se o valor de um elemento é repetido em arr2 , ele precisa estar em arr1 um número igual de vezes. Qual é a melhor maneira de fazer isso?

 arr1 = [1, 2, 3, 4] arr2 = [1, 2] checkSuperbag(arr1, arr2) > true //both 1 and 2 are in arr1 arr1 = [1, 2, 3, 4] arr2 = [1, 2, 5] checkSuperbag(arr1, arr2) > false //5 is not in arr1 arr1 = [1, 2, 3] arr2 = [1, 2, 3, 3] checkSuperbag(arr1, arr2) > false //3 is not in arr1 twice 

Uma opção é classificar os dois arrays e, em seguida, percorrer os dois, comparando os elementos. Se um elemento no candidato a sub-bolsa não for encontrado no super-saco, o primeiro não é uma sub-bolsa. A sorting é geralmente O (n * log (n)) e a comparação é O (max (s, t)), onde s e t são os tamanhos da matriz, para uma complexidade de tempo total de O (m * log (m)) , onde m = max (s, t).

 function superbag(sup, sub) { sup.sort(); sub.sort(); var i, j; for (i=0,j=0; i 

Se os elementos no código real forem inteiros, você pode usar um algoritmo de ordenação de inteiros de finalidade especial (como ordenação radix ) para uma complexidade geral de tempo O (max (s, t)), embora se os pacotes forem pequenos, -em Array.sort provavelmente irá executar mais rápido do que uma sorting de inteiro personalizado.

Uma solução com complexidade de tempo potencialmente menor é criar um tipo de bolsa. Sacos inteiros são particularmente fáceis. Inverta as matrizes existentes para as malas: crie um object ou uma matriz com os inteiros como chaves e uma contagem de repetição para os valores. Usar uma matriz não desperdiçará espaço criando como matrizes são escassas em JavaScript . Você pode usar as operações de sacolas para verificações de sub-sacola ou super-sacola. Por exemplo, subtraia o super do sub candidato e teste se o resultado não está vazio. Alternativamente, a operação de contenção deve ser O (1) (ou possivelmente O (log (n))), dando um loop sobre o candidato a sub-bolsa e testando se a contenção de super-saco excede a contenção da sub-bolsa para cada sub-bolsa elemento deve ser O (n) ou O (n * log (n)).

O seguinte não foi testado. Implementação do isInt deixado como exercício.

 function IntBag(from) { if (from instanceof IntBag) { return from.clone(); } else if (from instanceof Array) { for (var i=0; i < from.length) { this.add(from[i]); } } else if (from) { for (p in from) { /* don't test from.hasOwnProperty(p); all that matters is that p and from[p] are ints */ if (isInt(p) && isInt(from[p])) { this.add(p, from[p]); } } } } IntBag.prototype=[]; IntBag.prototype.size=0; IntBag.prototype.clone = function() { var clone = new IntBag(); this.each(function(i, count) { clone.add(i, count); }); return clone; }; IntBag.prototype.contains = function(i) { if (i in this) { return this[i]; } return 0; }; IntBag.prototype.add = function(i, count) { if (!count) { count = 1; } if (i in this) { this[i] += count; } else { this[i] = count; } this.size += count; }; IntBag.prototype.remove = function(i, count) { if (! i in this) { return; } if (!count) { count = 1; } this[i] -= count; if (this[i] > 0) { // element is still in bag this.size -= count; } else { // remove element entirely this.size -= count + this[i]; delete this[i]; } }; IntBag.prototype.each = function(f) { var i; foreach (i in this) { f(i, this[i]); } }; IntBag.prototype.find = function(p) { var result = []; var i; foreach (i in this.elements) { if (p(i, this[i])) { return i; } } return null; }; IntBag.prototype.sub = function(other) { other.each(function(i, count) { this.remove(i, count); }); return this; }; IntBag.prototype.union = function(other) { var union = this.clone(); other.each(function(i, count) { if (union.contains(i) < count) { union.add(i, count - union.contains(i)); } }); return union; }; IntBag.prototype.intersect = function(other) { var intersection = new IntBag(); this.each(function (i, count) { if (other.contains(i)) { intersection.add(i, Math.min(count, other.contains(i))); } }); return intersection; }; IntBag.prototype.diff = function(other) { var mine = this.clone(); mine.sub(other); var others = other.clone(); others.sub(this); mine.union(others); return mine; }; IntBag.prototype.subbag = function(super) { return this.size <= super.size && null !== this.find( function (i, count) { return super.contains(i) < this.contains(i); })); }; 

Veja também " comparando matrizes de javascript " para um exemplo de implementação de um conjunto de objects, caso você deseje proibir a repetição de elementos.

Você tem que suportar navegadores ruins? Se não, a function every deve facilitar isso.

Se arr1 é um superconjunto de arr2, então cada membro em arr2 deve estar presente em arr1

 var isSuperset = arr2.every(function(val) { return arr1.indexOf(val) >= 0; }); 

Aqui está um violino

EDITAR

Então você está definindo um superconjunto tal que para cada elemento em arr2, ocorre em arr1 o mesmo número de vezes? Acho que o filtro vai ajudar você a fazer isso (pegue o shim do link MDN anterior para suportar navegadores mais antigos):

 var isSuperset = arr2.every(function (val) { var numIn1 = arr1.filter(function(el) { return el === val; }).length; var numIn2 = arr2.filter(function(el) { return el === val; }).length; return numIn1 === numIn2; }); 

Fiddle atualizado

END EDIT


Se você quiser oferecer suporte a navegadores mais antigos, o link MDN acima tem um shim que você pode adicionar, o qual eu reproduzo aqui para sua conveniência:

 if (!Array.prototype.every) { Array.prototype.every = function(fun /*, thisp */) { "use strict"; if (this == null) throw new TypeError(); var t = Object(this); var len = t.length >>> 0; if (typeof fun != "function") throw new TypeError(); var thisp = arguments[1]; for (var i = 0; i < len; i++) { if (i in t && !fun.call(thisp, t[i], i, t)) return false; } return true; }; } 

EDITAR

Observe que esse será um algoritmo O (N2), portanto, evite executá-lo em grandes matrizes.

Ninguém postou uma function recursiva ainda e esses são sempre divertidos. Chame como arr1.containsArray( arr2 ) .

Demonstração: http://jsfiddle.net/ThinkingStiff/X9jed/

 Array.prototype.containsArray = function ( array /*, index, last*/ ) { if( arguments[1] ) { var index = arguments[1], last = arguments[2]; } else { var index = 0, last = 0; this.sort(); array.sort(); }; return index == array.length || ( last = this.indexOf( array[index], last ) ) > -1 && this.containsArray( array, ++index, ++last ); }; 

O uso de objects (leia-se: tabelas de hash) em vez da sorting deve reduzir a complexidade amortizada para O (m + n):

 function bagContains(arr1, arr2) { var o = {} var result = true; // Count all the objects in container for(var i=0; i < arr1.length; i++) { if(!o[arr1[i]]) { o[arr1[i]] = 0; } o[arr1[i]]++; } // Subtract all the objects in containee // And exit early if possible for(var i=0; i < arr2.length; i++) { if(!o[arr2[i]]) { o[arr2[i]] = 0; } if(--o[arr2[i]] < 0) { result = false; break; } } return result; } console.log(bagContains([1, 2, 3, 4], [1, 3])); console.log(bagContains([1, 2, 3, 4], [1, 3, 3])); console.log(bagContains([1, 2, 3, 4], [1, 3, 7])); 

Que produz true , false , false .

Encontrei isso na biblioteca do github lodash . Esta function usa funções incorporadas para resolver o problema. .includes() , .indexOf() e .every()

 var array1 = ['A', 'B', 'C', 'D', 'E']; var array2 = ['B', 'C', 'E']; var array3 = ['B', 'C', 'Z']; var array4 = []; function arrayContainsArray (superset, subset) { if (0 === subset.length) { return false; } return subset.every(function (value) { return (superset.includes(value)); }); } function arrayContainsArray1 (superset, subset) { if (0 === subset.length) { return false; } return subset.every(function (value) { return (superset.indexOf(value) >= 0); }); } console.log(arrayContainsArray(array1,array2)); //true console.log(arrayContainsArray(array1,array3)); //false console.log(arrayContainsArray(array1,array4)); //false console.log(arrayContainsArray1(array1,array2)); //true console.log(arrayContainsArray1(array1,array3)); //false console.log(arrayContainsArray1(array1,array4)); //false 

Quanto a outra abordagem, você pode fazer o seguinte;

 function checkIn(a,b){ return b.every(function(e){ return e === this.splice(this.indexOf(e),1)[0]; }, a.slice()); // a.slice() is the "this" in the every method } var arr1 = [1, 2, 3, 4], arr2 = [1, 2], arr3 = [1,2,3,3]; console.log(checkIn(arr1,arr2)); console.log(checkIn(arr1,arr3)); 

Se arr2 é subconjunto de arr1, então Length of set(arr1 + arr2) == Length of set(arr1)

 var arr1 = [1, 'a', 2, 'b', 3]; var arr2 = [1, 2, 3]; Array.from(new Set(arr1)).length == Array.from(new Set(arr1.concat(arr2))).length 

Solução rápida aqui pegue dois arrays se b for maior que não pode ser um super set então retorne false. Em seguida, percorra b para ver se a contém o elemento. Se assim for, exclua-o de a e continue se não retornar falso. Pior cenário é se b é um subconjunto, então o tempo será b.length .

 function isSuper(a,b){ var l=b.length,i=0,c; if(l>a.length){return false} else{ for(i;i-1){ a.splice(c,1); } else{return false} } return true; } } 

Isso pressupõe que as inputs nem sempre estarão em ordem e se a é 1,2,3 b é 3,2,1 ela ainda retornará verdadeira.

versão pequena:

 function checkSuperbag(arr1, arr2) { return !!~arr2.join('').indexOf(arr1.join('')) } 

Aqui está a minha solução:

 Array.prototype.containsIds = function (arr_ids) { var status = true; var current_arr = this; arr_ids.forEach(function(id) { if(!current_arr.includes(parseInt(id))){ status = false; return false; // exit forEach } }); return status; }; // Examples [1,2,3].containsIds([1]); // true [1,2,3].containsIds([2,3]); // true [1,2,3].containsIds([3,4]); // false