work Tentando resolver a diferença simétrica usando Javascript




set intersection js (12)

Estou tentando descobrir uma solução para diferença simétrica usando javascript que realiza os seguintes objetivos:

  • aceita um número não especificado de matrizes como argumentos
  • preserva a ordem original dos números nas matrizes
  • não remove duplicatas de números em matrizes únicas
  • remove duplicatas que ocorrem entre matrizes

Assim, por exemplo, se a entrada for ([1, 1, 2, 6], [2, 3, 5], [2, 3, 4]), a solução seria: [1, 1, 6, 5 4]

Estou tentando resolver isso como um desafio dado por uma comunidade de codificação online. As instruções exatas do estado de desafio,

Crie uma função que use duas ou mais matrizes e retorne uma matriz da diferença simétrica das matrizes fornecidas.

O termo matemático diferença simétrica refere-se aos elementos em dois conjuntos que estão no primeiro ou no segundo conjunto, mas não em ambos.

Embora minha solução abaixo encontre os números exclusivos de cada matriz, elimina todos os números que ocorrem mais de uma vez e não mantém a ordem dos números.

Minha pergunta é muito parecida com a que foi encontrada na diferença simétrica / elementos únicos em várias matrizes em javascript . No entanto, a solução não preserva a ordem original dos números e não preserva duplicatas de números exclusivos que ocorrem em matrizes únicas.

function sym(args){
    var arr = [];
    var result = [];
    var units;
    var index = {};
    for(var i in arguments){
        units = arguments[i];

    for(var j = 0; j < units.length; j++){
         arr.push(units[j]);
        }
    }

    arr.forEach(function(a){
        if(!index[a]){
            index[a] = 0;
        }
            index[a]++;

    });

       for(var l in index){
           if(index[l] === 1){
               result.push(+l);
           }
       }

    return result;
}
symsym([1, 1, 2, 6], [2, 3, 5], [2, 3, 4]); // => Desired answer: [1, 1, 6. 5. 4]

// Set difference, a.k.a. relative compliment
const diff = (a, b) => a.filter(v => !b.includes(v))

const symDiff = (first, ...rest) => rest.reduce((acc, x) => [
  ...diff(acc, x), 
  ...diff(x, acc)
], first)    

/* - - - */
console.log(symDiff([1, 3], ['Saluton', 3]))    // [1, 'Saluton']
console.log(symDiff([1, 3], [2, 3], [2, 8, 5])) // [1, 8, 5]


Solução javascript pura.

function diff(arr1, arr2) {
var arr3= [];
  for(var i = 0; i < arr1.length; i++ ){
    var unique = true;
     for(var j=0; j < arr2.length; j++){
          if(arr1[i] == arr2[j]){
               unique = false;
               break;
          }
     }
  if(unique){
    arr3.push(arr1[i]);}
  }
 return arr3;
}

function symDiff(arr1, arr2){
  return diff(arr1,arr2).concat(diff(arr2,arr1));
}

symDiff([1, "calf", 3, "piglet"], [7, "filly"])
//[1, "calf", 3, "piglet", 7, "filly"]

Eu me deparei com essa pergunta em minha pesquisa do mesmo desafio de codificação na FCC. Consegui resolvê-lo usando loops for e while , mas tive alguns problemas para resolver usando o Array.reduce() recomendado. Depois de aprender muito sobre o .reduce e outros métodos de array, pensei em compartilhar minhas soluções também.

Esta é a primeira maneira que eu resolvi, sem usar .reduce .

function sym() {
  var arrays = [].slice.call(arguments);

  function diff(arr1, arr2) {
    var arr = [];

    arr1.forEach(function(v) {
      if ( !~arr2.indexOf(v) && !~arr.indexOf(v) ) {
        arr.push( v );
      }
    });

    arr2.forEach(function(v) {
      if ( !~arr1.indexOf(v) && !~arr.indexOf(v) ) {
        arr.push( v );
      }
    });
    return arr;
  }

  var result = diff(arrays.shift(), arrays.shift());

  while (arrays.length > 0) {
    result = diff(result, arrays.shift());
  }

  return result;
}

Depois de aprender e tentar várias combinações de métodos, eu vim com isso que acho bem sucinto e legível.

function sym() {
  var arrays = [].slice.call(arguments);

  function diff(arr1, arr2) {
    return arr1.filter(function (v) {
      return !~arr2.indexOf(v);
    });
  }

  return arrays.reduce(function (accArr, curArr) { 
    return [].concat( diff(accArr, curArr), diff(curArr, accArr) )
    .filter(function (v, i, self) { return self.indexOf(v) === i; });
  });

}

Na última linha .filter , achei muito legal desduplicar uma matriz. Eu o encontrei here , mas o modifiquei para usar o terceiro parâmetro de retorno de chamada em vez da matriz nomeada devido ao encadeamento do método.

Este desafio foi muito divertido!


Outra solução simples, porém legível:

 
/*
This filters arr1 and arr2 from elements which are in both arrays
and returns concatenated results from filtering.
*/
function symDiffArray(arr1, arr2) {
  return arr1.filter(elem => !arr2.includes(elem))
             .concat(arr2.filter(elem => !arr1.includes(elem)));
}

/*
Add and use this if you want to filter more than two arrays at a time.
*/
function symDiffArrays(...arrays) {
  return arrays.reduce(symDiffArray, []);
}

console.log(symDiffArray([1, 3], ['Saluton', 3])); // [1, 'Saluton']
console.log(symDiffArrays([1, 3], [2, 3], [2, 8, 5])); // [1, 8, 5]

Funções usadas: Array.prototype.filter() | Array.prototype.reduce() | Array.prototype.includes()


Aqui está uma versão que usa o objeto Set para facilitar a pesquisa. Aqui está a lógica básica:

  1. Ele coloca cada matriz passada como argumento em um objeto Set separado (para facilitar a pesquisa rápida).
  2. Em seguida, itera cada passada na matriz e a compara com os outros objetos Set (os que não foram criados a partir da matriz que está sendo iterada).
  3. Se o item não for encontrado em nenhum dos outros Conjuntos, ele será adicionado ao resultado.

Então, começa com a primeira matriz [1, 1, 2, 6] . Como 1 não é encontrado em nenhuma das outras matrizes, cada um dos dois primeiros 1 valores é adicionado ao resultado. Em seguida, 2 é encontrado no segundo conjunto para que não seja adicionado ao resultado. Em seguida, 6 não é encontrado em nenhum dos outros dois conjuntos, portanto é adicionado ao resultado. O mesmo processo se repete para a segunda matriz [2, 3, 5] onde 2 e 3 são encontrados em outros Conjuntos, mas 5 não é assim, 5 é adicionado ao resultado. E, para a última matriz, apenas 4 não é encontrado nos outros conjuntos. Então, o resultado final é [1,1,6,5,4] .

Os objetos Set são usados ​​para conveniência e desempenho. Pode-se usar .indexOf() para procurá-los em cada matriz ou pode-se fazer sua própria pesquisa do tipo Set com um objeto simples, se você não quiser confiar no objeto Set. Há também um polyfill parcial para o objeto Set que funcionaria aqui nesta resposta .

function symDiff() {
    var sets = [], result = [];
    // make copy of arguments into an array
    var args = Array.prototype.slice.call(arguments, 0);
    // put each array into a set for easy lookup
    args.forEach(function(arr) {
        sets.push(new Set(arr));
    });
    // now see which elements in each array are unique 
    // e.g. not contained in the other sets
    args.forEach(function(array, arrayIndex) {
        // iterate each item in the array
        array.forEach(function(item) {
            var found = false;
            // iterate each set (use a plain for loop so it's easier to break)
            for (var setIndex = 0; setIndex < sets.length; setIndex++) {
                // skip the set from our own array
                if (setIndex !== arrayIndex) {
                    if (sets[setIndex].has(item)) {
                        // if the set has this item
                        found = true;
                        break;
                    }
                }
            }
            if (!found) {
                result.push(item);
            }
        });
    });
    return result;
}

var r = symDiff([1, 1, 2, 6], [2, 3, 5], [2, 3, 4]);
log(r);

function log(x) {
    var d = document.createElement("div");
    d.textContent = JSON.stringify(x);
    document.body.appendChild(d);
}

Uma parte importante desse código é como ele compara um determinado item aos conjuntos das outras matrizes. Ele apenas percorre a lista de objetos Set, mas ignora o objeto Set que possui o mesmo índice na matriz que a matriz que está sendo iterada. Isso ignora o conjunto criado a partir dessa matriz e, portanto, procura apenas itens que existem em outras matrizes. Isso permite reter duplicatas que ocorrem em apenas uma matriz.

Aqui está uma versão que usa o objeto Set se estiver presente, mas insere uma substituição pequenina, se não (portanto, isso funcionará em navegadores mais antigos):

function symDiff() {
    var sets = [], result = [], LocalSet;
    if (typeof Set === "function") {
        try {
            // test to see if constructor supports iterable arg
            var temp = new Set([1,2,3]);
            if (temp.size === 3) {
                LocalSet = Set;
            }
        } catch(e) {}
    }
    if (!LocalSet) {
        // use teeny polyfill for Set
        LocalSet = function(arr) {
            this.has = function(item) {
                return arr.indexOf(item) !== -1;
            }
        }
    }
    // make copy of arguments into an array
    var args = Array.prototype.slice.call(arguments, 0);
    // put each array into a set for easy lookup
    args.forEach(function(arr) {
        sets.push(new LocalSet(arr));
    });
    // now see which elements in each array are unique 
    // e.g. not contained in the other sets
    args.forEach(function(array, arrayIndex) {
        // iterate each item in the array
        array.forEach(function(item) {
            var found = false;
            // iterate each set (use a plain for loop so it's easier to break)
            for (var setIndex = 0; setIndex < sets.length; setIndex++) {
                // skip the set from our own array
                if (setIndex !== arrayIndex) {
                    if (sets[setIndex].has(item)) {
                        // if the set has this item
                        found = true;
                        break;
                    }
                }
            }
            if (!found) {
                result.push(item);
            }
        });
    });
    return result;
}


var r = symDiff([1, 1, 2, 6], [2, 3, 5], [2, 3, 4]);
log(r);

function log(x) {
    var d = document.createElement("div");
    d.textContent = JSON.stringify(x);
    document.body.appendChild(d);
}


Alternativa: use a pesquisa dentro de um mapa em vez de uma matriz

function sym(...vs){
    var has = {};
    //flatten values
    vs.reduce((a,b)=>a.concat(b)).
        //if element does not exist add it (value==1)
        //or mark it as multiply found value > 1
        forEach(value=>{has[value] = (has[value]||0)+1});
    return Object.keys(has).filter(x=>has[x]==1).map(x=>parseInt(x,10));
}
console.log(sym([1, 2, 3], [5, 2, 1, 4],[5,7], [5]));//[3,4,7])

Este é o código JS usando funções de ordem superior

    function sym(args) {
      var output;
      output = [].slice.apply(arguments).reduce(function(previous, current) {
        current.filter(function(value, index, self) { //for unique
          return self.indexOf(value) === index;
        }).map(function(element) { //pushing array
          var loc = previous.indexOf(element);
          a = [loc !== -1 ? previous.splice(loc, 1) : previous.push(element)];
        });
        return previous;
      }, []);
      document.write(output);
      return output;
    }

    sym([1, 2, 3], [5, 2, 1, 4]);

E retornaria a saída como: [3,5,4]


Apenas use _.xor ou copie o código lodash.


Minha pequena solução. No final, removi duplicatas por filter ().

function sym() {
  var args = Array.prototype.slice.call(arguments);
  var almost = args.reduce(function(a,b){
    return b.filter(function(i) {return a.indexOf(i) < 0;})
    .concat(a.filter(function(i){return b.indexOf(i)<0;}));
  });
  return almost.filter(function(el, pos){return almost.indexOf(el) == pos;});
}

sym([1, 1, 2, 5], [2, 2, 3, 5], [3, 4, 5, 5]);

//Result: [4,5,1]

Ei, se alguém estiver interessado, esta é a minha solução:

function sym (...args) {
  let fileteredArgs = [];
  let symDiff = [];
  args.map(arrayEl =>
    fileteredArgs.push(arrayEl.filter((el, key) =>
      arrayEl.indexOf(el) === key
      )
    )
  );

  fileteredArgs.map(elArr => {
    elArr.map(el => {
      let index = symDiff.indexOf(el);
      if (index === -1) {
        symDiff.push(el);
      } else {
        symDiff.splice(index, 1);
      }
    });
  });

  return (symDiff);
}

console.log(sym([1, 2, 3, 3], [5, 2, 1, 4]));


Como em todos os problemas, é melhor começar a escrever um algoritmo:

Concatene versões das matrizes, onde cada matriz é filtrada para conter os elementos que nenhuma matriz além da atual contém

Em seguida, basta escrever isso em JS:

function sym() {
  var arrays = [].slice.apply(arguments);

  return [].concat.apply([],               // concatenate
    arrays.map(                            // versions of the arrays
      function(array, i) {                 // where each array
        return array.filter(               // is filtered to contain
          function(elt) {                  // those elements which
            return !arrays.some(           // no array
              function(a, j) {             // 
                return i !== j             // other than the current one
                  && a.indexOf(elt) >= 0   // contains
                ;
              }
            );
          }
        );
      }
    )
  );
}

Versão sem comentários, escrita de forma mais sucinta usando o ES6:

function sym(...arrays) {
  return [].concat(arrays . 
    map((array, i) => array . 
      filter(elt => !arrays . 
        some((a, j) => i !== j && a.indexOf(elt) >= 0))));
}

function sym(arr1, arr2, ...rest) {

  //creating a array which has unique numbers from both the arrays
  const union = [...new Set([...arr1,...arr2])];

  // finding the Symmetric Difference between those two arrays
  const diff= union.filter((num)=>!(arr1.includes(num)&&arr2.includes(num)))

  //if there are more than 2 arrays
  if(rest.length){
    // recurrsively call till rest become 0 
    // i.e.  diff of 1,2 will be the first parameter so every recurrsive call will reduce     //  the arrays till diff between all of them are calculated.

    return sym(diff, rest[0], ...rest.slice(1))
  }
  return diff
}






symmetric-difference