Estoy buscando una función que devuelva verdadero si y solo si una matriz dada incluye todos los elementos de otra matriz de destino que puede incluir dos o más ocurrencias del mismo elemento.
Data de muestra:
const target = [ 1, 3, 3 ]; const array1 = [ 1, 2, 3, 4 ]; // false const array2 = [ 1, 3, 3, 4 ]; // true const array3 = [ 1, 3, 4, 3 ]; // true const array4 = [ 3, 2, 1, 3 ]; // true const array5 = [ 1, 1, 3, 3 ]; // trueLa respuesta de esta pregunta está cerca pero no tiene en cuenta los duplicados en la matriz de destino.
La respuesta de esta pregunta funciona para Ruby, pero estoy buscando una solución de Javascript.
Cuando no se tienen en cuenta los duplicados, .indexOf() e .includes() lo hacen bastante fácil y hay soluciones elegantes de una sola línea. Pero no estoy seguro de cómo realizar un seguimiento de los duplicados y sospecho que se necesita un enfoque más iterativo.
const isMultiSubset = (target, value) => { const occurences = new Map; for(const entry of target) occurences.set(entry, (occurences.get(entry) ?? 0) + 1); for(const entry of value) if (occurences.has(entry)) occurences.set(entry, occurences.get(entry) - 1); return [...occurences.values()].every(count => count <= 0); };Al usar un Mapa para contar las ocurrencias, esto se puede resolver en O (n + m).
De manera similar al comentario de @Barmar, también puede recorrer los elementos que desea incluir y eliminarlos del objetivo, si están presentes e inmediatamente devolver falso si uno de ellos no está presente. Si se encontraron todos los elementos deseados, devuelva verdadero.
Aviso: esto tiene una complejidad de tiempo O (n * m), la solución de @ Jonas tiene una mejor complejidad de tiempo.
function includesMulti(elements, inArray) { const unmatched = inArray.slice(); for (const element of elements) { const matchIndex = unmatched.indexOf(element); if (matchIndex === -1) return false; unmatched.splice(matchIndex, 1); } return true; } const target = [ 1, 3, 3 ]; const array1 = [ 1, 2, 3, 4 ]; // false const array2 = [ 1, 3, 3, 4 ]; // true const array3 = [ 1, 3, 4, 3 ]; // true const array4 = [ 3, 2, 1, 3 ]; // true const array5 = [ 1, 1, 3, 3 ]; // true const array6 = [ 1, 1, 3, 3]; // true console.log(includesMulti(target, array1)); console.log(includesMulti(target, array2)); console.log(includesMulti(target, array3)); console.log(includesMulti(target, array4)); console.log(includesMulti(target, array5)); console.log(includesMulti(target, array6));Un refinamiento de este enfoque que evita clonar y volver a escanear la matriz para buscar podría ser el siguiente: para cada elemento a buscar, recuerde dónde se encontró por última vez, utilícelo como compensación para la siguiente búsqueda indexOf.
function includesMulti(elements, inArray) { const lastMatches = new Map(); for (const element of elements) { const previousMatchIndex = lastMatches.get(element); const matchIndex = inArray.indexOf(element, previousMatchIndex + 1); if (matchIndex === -1) return false; lastMatches.set(element, matchIndex); } return true; } const target = [ 1, 3, 3 ]; const array1 = [ 1, 2, 3, 4 ]; // false const array2 = [ 1, 3, 3, 4 ]; // true const array3 = [ 1, 3, 4, 3 ]; // true const array4 = [ 3, 2, 1, 3 ]; // true const array5 = [ 1, 1, 3, 3 ]; // true const array6 = [ 1, 1, 3, 3]; // true console.log(includesMulti(target, array1)); console.log(includesMulti(target, array2)); console.log(includesMulti(target, array3)); console.log(includesMulti(target, array4)); console.log(includesMulti(target, array5)); console.log(includesMulti(target, array6)); Aquí hay un pequeño truco: cuando no se encontró una coincidencia anterior, map.get devuelve undefined y luego previousMatchIndex+1 es NaN , que indexOf . Para ser más explícito, es posible que desee reemplazar eso por previousMatchIndex === undefined ? 0 : (previousMatchIndex+1) .
Algo como esto tal vez. Funciona, pero no es el más eficaz.
const target = [1, 3, 3]; const array1 = [1, 2, 3, 4]; // false const array2 = [1, 3, 3, 4]; // true const array3 = [1, 3, 4, 3]; // true const array4 = [3, 2, 1, 3]; // true const testArray = (arr1, arr2) => { const countOccurrences = (arrayToCount) => { return arrayToCount.reduce((acc, e) => { acc[e] ? (acc[e] = { count: acc[e].count + 1 }) : (acc[e] = { count: 1 }); return acc; }, {}); }; let reduced = countOccurrences(arr1); let reduced2 = countOccurrences(arr2); const result = Object.keys(reduced).reduce((acc, e) => { if (!acc) return false; if (!reduced2[e]) return false; if (reduced2[e].count < reduced[e].count) return false; return acc; }, true); return result; }; console.log(testArray(target, array1)); console.log(testArray(target, array2)); console.log(testArray(target, array3)); console.log(testArray(target, array4));