Determine if one array contains all elements of another array, including any duplicates-CodePudding

I'm looking for a function that returns true if and only if a given array includes all the elements of another target array which may include two or more occurrences of the same element.

Sample data:

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

This question's answer is close but doesn't account for duplicates in target array.

This question's answer works for Ruby but I'm looking for a Javascript solution.

When not accounting for duplicates, .indexOf() and .includes() make it rather easy and there are elegant one-liner solutions. But I'm unsure how to keep track of duplicates and suspect a more iterative approach is needed.

CodePudding user response：

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

By using a Map to count occurences this can be solved in O(n m).

CodePudding user response：

Something like this maybe. It works but it is not the most performant.

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

CodePudding user response：

Similar to @Barmar's comment, you might also loop over the elements you want to have included and remove them from the target, if they are present and immediately return false if one of them is not present. If every desired element was found, return true.

Notice: this has time complexity O(n*m), @Jonas' solution has better time complexity.

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

A refinement of this approach which avoids cloning and rescanning the array to search in could be the following: for each element to look for remember where it was found last use that as the offset for the next indexOf search.

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

There is a little trick in here: when no previous match was found, undefined is returned from map.get and then previousMatchIndex 1 is NaN which is ignored by indexOf. To be more explicit, you might want to replace that by previousMatchIndex === undefined ? 0 : (previousMatchIndex 1).

CodePudding user response：

You can use the filter method and check if the length of the filtered array is the same as the target array. This will work with duplicate values.

const compareArrays = (target, array) => array.filter((x, i) => x === target[i]).length === target.length;

compareArrays(target, array1); // false
compareArrays(target, array2); // true