Compruebe si cada elemento de una matriz está en una segunda matriz
Tengo dos matrices y quiero comprobar si todos los elementos arr2están en arr1. Si el valor de un elemento se repite en arr2, debe repetirse arr1el mismo número de veces. ¿Cuál es la mejor manera de hacer esto?
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
¿Tienes que admitir navegadores de mala calidad? Si no, todas las funciones deberían facilitarlo.
Si arr1 es un superconjunto de arr2, entonces cada miembro de arr2 debe estar presente en arr1.
var isSuperset = arr2.every(function(val) { return arr1.indexOf(val) >= 0; });
Aquí hay un violín
EDITAR
Entonces, ¿estás definiendo un superconjunto de modo que para cada elemento en arr2, aparezca en arr1 la misma cantidad de veces? Creo que el filtro te ayudará a hacerlo (toma la corrección del enlace MDN anterior para admitir navegadores más antiguos):
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;
});
Violín actualizado
FINALIZAR EDITAR
Si desea admitir navegadores más antiguos, el enlace MDN anterior tiene una corrección que puede agregar, que reproduzco aquí para su conveniencia:
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
Tenga en cuenta que este será un algoritmo O(N 2 ), así que evite ejecutarlo en matrices grandes.
Una opción es ordenar las dos matrices y luego recorrer ambas para comparar elementos. Si un elemento del candidato a subbolsa no se encuentra en la superbolsa, el primero no es una subbolsa. La clasificación es generalmente O(n*log(n)) y la comparación es O(max(s,t)), donde s y t son los tamaños de matriz, para una complejidad de tiempo total de O(m*log(m)) , donde m=max(s,t).
function superbag(sup, sub) {
sup.sort();
sub.sort();
var i, j;
for (i=0,j=0; i<sup.length && j<sub.length;) {
if (sup[i] < sub[j]) {
++i;
} else if (sup[i] == sub[j]) {
++i; ++j;
} else {
// sub[j] not in sup, so sub not subbag
return false;
}
}
// make sure there are no elements left in sub
return j == sub.length;
}
Si los elementos en el código real son números enteros, puede usar un algoritmo de clasificación de enteros de propósito especial (como radix sort ) para una complejidad de tiempo general O(max(s,t)), aunque si las bolsas son pequeñas, las bolsas construidas -in Array.sortprobablemente se ejecutará más rápido que una ordenación de enteros personalizada.
Una solución con una complejidad de tiempo potencialmente menor es crear un tipo de bolsa. Las bolsas de números enteros son particularmente fáciles. Voltee las matrices existentes para las bolsas: cree un objeto o una matriz con los números enteros como claves y un recuento repetido para los valores. El uso de una matriz no desperdiciará espacio al crearla, ya que las matrices son escasas en Javascript . Puede utilizar operaciones de bolsa para comprobaciones de subbolsas o superbolsas. Por ejemplo, reste el super del sub candidato y pruebe si el resultado no está vacío. Alternativamente, la containsoperación debe ser O(1) (o posiblemente O(log(n))), por lo que se realiza un bucle sobre el candidato a subbolsa y se prueba si la contención de la súper bolsa excede la contención de la subbolsa para cada elemento de la subbolsa. debe ser O(n) u O(n*log(n)).
Lo siguiente no está probado. Implementación de isIntla izquierda como ejercicio.
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);
}));
};
Consulte también " comparar matrices de JavaScript " para ver un ejemplo de implementación de un conjunto de objetos, en caso de que alguna vez desee no permitir la repetición de elementos.
Nadie ha publicado una función recursiva todavía y siempre son divertidas. Llámalo como arr1.containsArray( arr2 ).
Demostración: 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 );
};
El uso de objetos (léase: tablas hash) en lugar de ordenarlos debería reducir la complejidad amortizada a 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]));
Cuyos rendimientos true, false, false.
Mar 20 '2013 23:03