Better way to check if an element only exists in one array-CodePudding

I need help with creating a function to return the elements that are only present in one of 3 arrays, for example

let arr1 = ['a', 'b', 'c', 'a', 'b']
let arr2 = ['a', 'd', 'b', 'c']
let arr3 = ['f', 'c', 'a']

In the three arrays above, 'd' and 'f' are found only in one of the arrays (arr2 and arr3), I need to return them.

['d','f']

The arrays can be of different sizes and the returned elements must not be duplicated.

I tried to find better alternatives, but I failed and just went with the brute force approach, looping through each array and checking if the element exists in the other two arrays, but obviously, it's really slow and hard to read.

function elementsInOnlyOneArr(a1, a2, a3) {

  let myArr = [];

  for(let el of a1){
    if(a2.includes(el) == false && a3.includes(el) == false && myArr.includes(el) == false){
      myArr.push(el);
    }
  }

  for(let el of a2){
    if(a1.includes(el) == false && a3.includes(el) == false && myArr.includes(el) == false){
      myArr.push(el);
    }
  }

  for(let el of a3){
    if(a2.includes(el) == false && a1.includes(el) == false && myArr.includes(el) == false){
      myArr.push(el);
    }
  }


  return myArr;
}

CodePudding user response：

Assuming there are less than 32 arrays, you can do this efficiently with bitmaps. Basically, build an index key -> number where the number has the Nth bit set if the key is in the Nth array. Finally return keys whose numbers only have a single bit set (=are powers of two):

function difference(...arrays) {
    let items = {}

    for (let [n, a] of arrays.entries())
        for (let x of a) {
            items[x] = (items[x] ?? 0) | (1 << n)
        }

    return Object.keys(items).filter(x => 
        Number.isInteger(Math.log2(items[x])))
}


let arr1 = ['a', 'b', 'c', 'a', 'b']
let arr2 = ['a', 'd', 'b', 'c']
let arr3 = ['f', 'c', 'a']

console.log(difference(arr1, arr2, arr3))

CodePudding user response：

EDIT: Misunderstood OP and it's not an intersect, but extracting values that are unique (e.g. NOT the intersection) between the individual arrays, for that this might work:

let arr1 = ['a', 'b', 'c', 'a', 'b'];
let arr2 = ['a', 'd', 'b', 'c'];
let arr3 = ['f', 'c', 'a'];

const thereCanOnlyBeOne = function(...arrs) {
    return Array.from(
        arrs.reduce((map, arr) => {
            arr.forEach((v) => map.set(v, map.get(v) 1));
            
            return map;
        }, new Map([...([].concat(...arrs).entries())].map(([index, value]) => [value, 0])))
    )
    .filter(([value, count]) => count === 1)
    .map(([value, count]) => value);
};

console.log(thereCanOnlyBeOne(arr1, arr2, arr3));

I would think @gog's answer is way more sophisticated and probably much faster, but i have a slightly hard time wrapping my head around it (call me stupid, i take it =D), so here's the breakdown of the slightly convoluted way of doing this with a Map and array methods:

pass all arrays to be analyzed into function, order doesn't matter
initialize Array.reduce() with a pre-configured map new Map([...([].concat(...arrs).entries())].map(([index, value]) => [value, 0])), i know it looks terrible but what it does is concatenating all arrays together into one single array containing all values, then getting tuples via .entries() (they'll contain [<index>, <value>]), flipping those around so they are now in the format [<value>, 0] (we don't need the index, so just set it to 0, it's gonna be a counter!) and create a new Map() from those tuples, we have ourselves a counter Map with all values (unique) that exist in all arrays, it's gonna look like this:

0: {"a" => 0}
1: {"b" => 0}
2: {"c" => 0}
3: {"d" => 0}
4: {"f" => 0}

Loop (i chose reduce, but any loop structure works) trough all input arrays and their values, counting up occurrences in the Map, at the end the Map will look as follows:

0: {"a" => 4}
1: {"b" => 3}
2: {"c" => 3}
3: {"d" => 1}
4: {"f" => 1}

Once done with that, we convert the Map back into an array via Array.from() creating an array of tuples:

[
   ["a", 4],
   ["b", 3],
   ["c", 3],
   ["d", 1],
   ["f", 1],
]

Filter that resulting array of tuples (now in the form of [<value>, <count>] to only be left with values that exactly occurred once, leaving us with:

[
   ["d", 1],
   ["f", 1],
]

Map over the filtered array to "dumb" it down into a one-dimensional array again and return the result:

["d", "f"]

WARNING: Internally this code does a ****load of loops, so call it a brute-force loop as well, it just looks "shorter" due to "sexy" ES6 array-syntax-sugar.

A slightly modified version for completeness as the Array.filter() step can be omitted by iterating the counter-Map once it's finalized and simply deleting Map-entries that do not have value 1. Not sure what is faster, would need some testing.

let arr1 = ['a', 'b', 'c', 'a', 'b'];
let arr2 = ['a', 'd', 'b', 'c'];
let arr3 = ['f', 'c', 'a'];

const thereCanOnlyBeOne = function(...arrs) {
    let result;
    
    arrs
    .reduce((map, arr) => {
        arr.forEach((v) => map.set(v, map.get(v) 1));
        
        return map;
    }, new Map([...([].concat(...arrs).entries())].map(([index, value]) => [value, 0])))
    // the result of .reduce will be a Map!
    .forEach((value, key, map) => { value !== 1 && map.delete(key); result = map; });
    
    return Array.from(result).map(([value, count]) => value);
};

console.log(thereCanOnlyBeOne(arr1, arr2, arr3));

CodePudding user response：

This is really just Set operations. The method single below finds any entry in a test array that does not appear in the other arrays in the collection. Deliberately implementing this so you can test individual arrays since it's not clear in the question if you need to return the letters, or the arrays.

let arr1 = ['a', 'b', 'c', 'a', 'b']
let arr2 = ['a', 'd', 'b', 'c']
let arr3 = ['f', 'c', 'a']

// The set of arrays
let arrays = [ arr1, arr2, arr3 ]

// Finds any entries in the test array that doesn't appear in the arrays that aren't the test arrays
let singles = (test) => {
  // others is the Set of all value in the other arrays
  others = arrays.reduce( ( accum, elem ) => {
    if (elem != test) { elem.forEach(accum.add, accum) }
    return accum
  }, new Set())
  // find anything in the test array that the others do not have
  return test.filter( value => ! others.has(value) )
}

// collect results from testing all arrays
result = []
for(const array of arrays) { result.push(...singles(array))
}
console.log(result)

Borrowing the parameter construction from @gog's excellent answer, you could also define it so that it takes a test array and an arbitrary collection of arrays to test against:

    let singles = (test, ...arrays) => {
      // others is the Set of all value in the other arrays
      others = arrays.reduce( ( accum, elem ) => {
        if (elem != test) { elem.forEach(accum.add, accum) }
        return accum
      }, new Set())
      // find anything in the test array that the others do not have
      return test.filter( value => ! others.has(value) )
    }

    console.log(singles(arr2, arr1, arr2, arr3))

The advantage here is that this should work with any number of arrays, while gog's answer is probably faster for a collection of less than 32 arrays (or technically any number if you were willing to extend it using BigInt, but that may lose some of the speed)

CodePudding user response：

This is a brute force iterator much like your own, but reduces the number of re-entries by removing items from the array:

function elementsInOnlyOneArr(...arrays) {

  // de-dup and sort so we process the longest array first
  let sortedArrays = arrays.map(ar => [...new Set(ar)]).sort((a,b) => b.length - a.length);
  
  for (let ai1 = 0 ; ai1 < sortedArrays.length; ai1   ) {
    for(let i = sortedArrays[ai1].length - 1; i >= 0; i --){
      let exists = false;
      let val = sortedArrays[ai1][i];   
      for(let ai2 = ai1   1 ; ai2 < sortedArrays.length ; ai2   ) {
        let foundIndex = sortedArrays[ai2].indexOf(val);
        if (foundIndex >= 0) {
          exists = true;
          sortedArrays[ai2].splice(foundIndex,1);
          // do not break, check for match in the other arrays
        }
      }
      // if there was a match in any of the other arrays, remove it from the first one too!
      if (exists)
        sortedArrays[ai1].pop();
    }
  }
  // concat the remaining elements, they are all unique
  let output = sortedArrays[0];
  for(let i = 1; i < sortedArrays.length; i   )
    output = output.concat(sortedArrays[i]);
    
  return output;
}

let arr1 = ['a', 'b', 'c', 'a', 'b']
let arr2 = ['a', 'd', 'b', 'c']
let arr3 = ['f', 'c', 'a']
console.log(elementsInOnlyOneArr(arr1,arr2,arr3));

See this fiddle: https://jsfiddle.net/9ab4Le7m/

CodePudding user response：

The Array.prototype.includes() method seems like the way to go here.

let arr1 = ['a', 'b', 'c', 'a', 'b']
let arr2 = ['a', 'd', 'b', 'c']
let arr3 = ['f', 'c', 'a']
var arrays = [arr1,arr2,arr3];
const items = arr1.concat(arr2, arr3);
let results = [];

items.map(isInOneArray);

function isInOneArray(item){
  let found = 0;
  for (const arr of arrays){
    if (arr.includes(item)){
      found   ;
    }
  }
  if (found===1){
    results.push(item);
  }
}
console.log(results);

CodePudding user response：

Do a diff of each of the array and concat those to get the unique values only in any one of the arrays.

const arr1 = ['a', 'b', 'c', 'a', 'b'];
const arr2 = ['a', 'd', 'b', 'c'];
const arr3 = ['f', 'c', 'a'];

function diff(a1, a2, a3) {
  let u1 = a1.filter(el => { return !a2.includes(el) })
  .filter(el => { return !a3.includes(el) });
  let u2 = a2.filter(el => { return !a1.includes(el) })
   .filter(el => { return !a3.includes(el) });
   let u3 = a3.filter(el => { return !a2.includes(el) })
   .filter(el => { return !a1.includes(el) });
  return u1.concat(u2).concat(u3);
}
/* diff them */
const adiff = diff(arr1, arr2, arr3);
console.log(adiff);