Tratando de resolver la diferencia simétrica usando Javascript
arrays symmetric-difference (15)
Estoy tratando de encontrar una solución para la diferencia simétrica usando JavaScript que cumpla con los siguientes objetivos:
- acepta un número no especificado de matrices como argumentos
- conserva el orden original de los números en las matrices
- no elimina duplicados de números en matrices individuales
- elimina los duplicados que ocurren en las matrices
Así, por ejemplo, si la entrada es ([1, 1, 2, 6], [2, 3, 5], [2, 3, 4]), la solución sería, [1, 1, 6, 5 4].
Estoy tratando de resolver esto como un desafío dado por una comunidad de codificación en línea. Las instrucciones exactas del estado del desafío,
Cree una función que tome dos o más matrices y devuelva una matriz de la diferencia simétrica de las matrices proporcionadas.
El término matemático diferencia simétrica se refiere a los elementos en dos conjuntos que están en el primer o segundo conjunto, pero no en ambos.
Aunque mi solución a continuación encuentra los números que son únicos para cada matriz, elimina todos los números que ocurren más de una vez y no mantiene el orden de los números.
Mi pregunta es muy parecida a la que se hace al encontrar diferencias simétricas / elementos únicos en múltiples matrices en javascript . Sin embargo, la solución no conserva el orden original de los números y no conserva duplicados de números únicos que ocurren en matrices individuales.
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]
Este es el código JS que utiliza funciones de orden 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]);
Y devolvería la salida como: [3,5,4]
Alternativa: utilice la búsqueda dentro de un mapa en lugar de una 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])
Aquí hay una versión que usa el objeto
Set
para hacer una búsqueda más rápida.
Aquí está la lógica básica:
- Coloca cada matriz pasada como argumento en un objeto Set separado (para facilitar la búsqueda rápida).
- Luego, itera cada pasada en la matriz y la compara con los otros objetos Set (los que no están hechos de la matriz que se está iterando).
- Si el elemento no se encuentra en ninguno de los otros Conjuntos, se agrega al resultado.
Entonces, comienza con la primera matriz
[1, 1, 2, 6]
.
Como
1
no se encuentra en ninguna de las otras matrices, cada uno de los dos primeros valores
1
se agrega al resultado.
Luego se encuentra
2
en el segundo conjunto, por lo que no se agrega al resultado.
Entonces
6
no se encuentra en ninguno de los otros dos conjuntos, por lo que se agrega al resultado.
El mismo proceso se repite para la segunda matriz
[2, 3, 5]
donde
2
y
3
se encuentran en otros Conjuntos, pero
5
no es así, se agrega
5
al resultado.
Y, para la última matriz, solo
4
no se encuentran en los otros Conjuntos.
Entonces, el resultado final es
[1,1,6,5,4]
.
Los objetos
Set
se usan por conveniencia y rendimiento.
Uno podría usar
.indexOf()
para buscarlos en cada matriz o uno podría hacer su propia búsqueda tipo Set con un objeto simple si no desea confiar en el objeto Set.
También hay un polyfill parcial para el objeto Set que funcionaría aquí en
esta respuesta
.
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);
}
Una parte clave de este código es cómo compara un elemento dado con los Conjuntos de las otras matrices. Simplemente itera a través de la lista de objetos Set, pero omite el objeto Set que tiene el mismo índice en la matriz que la matriz que se itera. Eso omite el conjunto creado a partir de esta matriz, por lo que solo busca elementos que existen en otras matrices. Eso le permite retener duplicados que ocurren en una sola matriz.
Aquí hay una versión que usa el objeto
Set
si está presente, pero inserta un pequeño reemplazo si no (para que esto funcione en navegadores más antiguos):
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);
}
Como con todos los problemas, es mejor comenzar escribiendo un algoritmo:
Concatenar versiones de las matrices, donde cada matriz se filtra para contener aquellos elementos que no contiene otra matriz que la actual.
Luego solo escribe eso en 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
;
}
);
}
);
}
)
);
}
Versión no comentada, escrita más sucintamente usando ES6:
function sym(...arrays) {
return [].concat(arrays .
map((array, i) => array .
filter(elt => !arrays .
some((a, j) => i !== j && a.indexOf(elt) >= 0))));
}
Cree un mapa con un recuento de todos los valores únicos (en todas las matrices). Luego concatene todas las matrices y filtre valores no únicos utilizando el Mapa.
const symsym = (...args) => {
// create a Map from the unique value of each array
const m = args.reduce((r, a) => {
// get unique values of array, and add to Map
new Set(a).forEach((n) => r.set(n, (r.get(n) || 0) + 1));
return r;
}, new Map());
// combine all arrays
return [].concat(...args)
// remove all items that appear more than once in the map
.filter((n) => m.get(n) === 1);
};
console.log(symsym([1, 1, 2, 6], [2, 3, 5], [2, 3, 4])); // => Desired answer: [1, 1, 6, 5, 4]
Encontré esta pregunta en mi investigación del mismo desafío de codificación en FCC.
Pude resolverlo usando bucles
for
y while, pero tuve algunos problemas para resolver usando el
Array.reduce()
recomendado.
Después de aprender un montón sobre
.reduce
y otros métodos de matriz, pensé que también compartiría mis soluciones.
Esta es la primera forma en que lo resolví, sin 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;
}
Después de aprender y probar varias combinaciones de métodos, se me ocurrió esto que creo que es bastante sucinto y legible.
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; });
});
}
Esa última línea
.filter
que pensé que era genial deducir una matriz.
Lo encontré
here
, pero lo modifiqué para usar el tercer parámetro de devolución de llamada en lugar de la matriz con nombre debido al encadenamiento del método.
¡Este desafío fue muy divertido!
Esto funciona para mi:
function sym() {
var args = [].slice.call(arguments);
var getSym = function(arr1, arr2) {
return arr1.filter(function(each, idx) {
return arr2.indexOf(each) === -1 && arr1.indexOf(each, idx + 1) === -1;
}).concat(arr2.filter(function(each, idx) {
return arr1.indexOf(each) === -1 && arr2.indexOf(each, idx + 1) === -1;
}));
};
var result = getSym(args[0], args[1]);
var len = args.length - 1, i = 2;
while (--len) {
result = [].concat(getSym(result, args[i]));
i++;
}
return result;
}
console.info(sym([1, 1, 2, 5], [2, 2, 3, 5], [6, 8], [7, 8], [9]));
Hola, si alguien está interesado, esta es mi solución:
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]));
Mi pequeña solución. Al final, eliminé duplicados 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]
Otra solución simple pero legible:
/*
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]
Funciones utilizadas: Array.prototype.filter() | Array.prototype.reduce() | Array.prototype.includes()
Simplemente use _.xor o copie el código lodash.
Solución 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"]
function sym(args) {
var initialArray = Array.prototype.slice.call(arguments);
var combinedTotalArray = initialArray.reduce(symDiff);
// Iterate each element in array, find values not present in other array and push values in combinedDualArray if value is not there already
// Repeat for the other array (change roles)
function symDiff(arrayOne, arrayTwo){
var combinedDualArray = [];
arrayOne.forEach(function(el, i){
if(!arrayTwo.includes(el) && !combinedDualArray.includes(el)){
combinedDualArray.push(el);
}
});
arrayTwo.forEach(function(el, i){
if(!arrayOne.includes(el) && !combinedDualArray.includes(el)){
combinedDualArray.push(el);
}
});
combinedDualArray.sort();
return combinedDualArray;
}
return combinedTotalArray;
}
console.log(sym([1, 1, 2, 5], [2, 2, 3, 5], [3, 4, 5, 5]));
// 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]
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
}