尝试使用 Javascript 解决对称差异

Trying to solve symmetric difference using Javascript

提问by davisec52

I am trying to figure out a solution for symmetric difference using javascript that accomplishes the following objectives:

我正在尝试使用实现以下目标的 javascript 找出对称差异的解决方案：

• accepts an unspecified number of arrays as arguments
• preserves the original order of the numbers in the arrays
• does not remove duplicates of numbers in single arrays
• removes duplicates occurring across arrays

• 接受未指定数量的数组作为参数
• 保留数组中数字的原始顺序
• 不会删除单个数组中的重复数字
• 删除数组中出现的重复项

Thus, for example, if the input is ([1, 1, 2, 6], [2, 3, 5], [2, 3, 4]), the solution would be, [1, 1, 6, 5, 4].

因此，例如，如果输入是 ([1, 1, 2, 6], [2, 3, 5], [2, 3, 4])，则解将是 [1, 1, 6, 5 , 4]。

I am trying to solve this as challenge given by an online coding community. The exact instructions of the challenge state,

我正在尝试解决这个问题，作为在线编码社区提出的挑战。挑战状态的确切说明，

Create a function that takes two or more arrays and returns an array of the symmetric difference of the provided arrays.

The mathematical term symmetric difference refers to the elements in two sets that are in either the first or second set, but not in both.

创建一个函数，该函数接受两个或多个数组并返回所提供数组的对称差的数组。

数学术语对称差是指两个集合中的元素属于第一组或第二组，但不属于两者。

Although my solution below finds the numbers that are unique to each array, it eliminates all numbers occuring more than once and does not keep the order of the numbers.

尽管我下面的解决方案找到了每个数组唯一的数字，但它消除了出现多次的所有数字并且不保持数字的顺序。

My question is very close to the one asked at finding symmetric difference/unique elements in multiple arrays in javascript. However, the solution does not preserve the original order of the numbers and does not preserve duplicates of unique numbers occurring in single arrays.

我的问题与在 javascript 中的多个数组中查找对称差异/唯一元素时提出的问题非常接近。但是，该解决方案不会保留数字的原始顺序，也不会保留出现在单个数组中的唯一数字的重复项。

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]

采纳答案by jfriend00

Here's a version that uses the Setobject to make for faster lookup. Here's the basic logic:

这是一个使用Set对象来加快查找速度的版本。这是基本逻辑：

1. It puts each array passed as an argument into a separate Set object (to faciliate fast lookup).
2. Then, it iterates each passed in array and compares it to the other Set objects (the ones not made from the array being iterated).
3. If the item is not found in any of the other Sets, then it is added to the result.

1. 它将作为参数传递的每个数组放入一个单独的 Set 对象（以促进快速查找）。
2. 然后，它迭代每个传入数组并将其与其他 Set 对象（不是由被迭代的数组组成的对象）进行比较。
3. 如果在任何其他 Sets 中未找到该项目，则将其添加到结果中。

So, it starts with the first array [1, 1, 2, 6]. Since 1is not found in either of the other arrays, each of the first two 1values are added to the result. Then 2is found in the second set so it is not added to the result. Then 6is not found in either of the other two sets so it is added to the result. The same process repeats for the second array [2, 3, 5]where 2and 3are found in other Sets, but 5is not so 5is added to the result. And, for the last array, only 4is not found in the other Sets. So, the final result is [1,1,6,5,4].

所以，它从第一个数组开始[1, 1, 2, 6]。由于1在其他任何一个数组中都没有找到，因此将前两个1值中的每一个添加到结果中。然后2在第二组中找到，因此不会添加到结果中。然后6在其他两组中都没有找到，因此将其添加到结果中。对第二个数组重复相同的过程，[2, 3, 5]其中2和3在其他集合中找到，但5不是这样5添加到结果中。并且，对于最后一个数组，只有4在其他集合中找不到。所以，最后的结果是[1,1,6,5,4]。

The Setobjects are used for convenience and performance. One could use .indexOf()to look them up in each array or one could make your own Set-like lookup with a plain object if you didn't want to rely on the Set object. There's also a partial polyfill for the Set object that would work here in this answer.

这些Set对象用于方便和性能。可以使用.indexOf()在每个数组中查找它们，或者如果您不想依赖 Set 对象，则可以使用普通对象进行类似 Set 的查找。Set 对象还有一个部分 polyfill，可以在此答案中使用。

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

One key part of this code is how it compares a given item to the Sets from the other arrays. It just iterates through the list of Set objects, but it skips the Set object that has the same index in the array as the array being iterated. That skips the Set made from this array so it's only looking for items that exist in other arrays. That allows it to retain duplicates that occur in only one array.

此代码的一个关键部分是它如何将给定项与其他数组中的 Set 进行比较。它只是遍历 Set 对象的列表，但会跳过在数组中与被迭代数组具有相同索引的 Set 对象。这会跳过由该数组构成的 Set，因此它只查找存在于其他数组中的项目。这允许它保留只出现在一个数组中的重复项。

---

---

Here's a version that uses the Setobject if it's present, but inserts a teeny replacement if not (so this will work in more older browsers):

这是一个版本，Set如果对象存在，则使用该对象，但如果不存在则插入一个很小的替换（因此这将适用于更旧的浏览器）：

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

回答by

As with all problems, it's best to start off writing an algorithm:

与所有问题一样，最好从编写算法开始：

Concatenate versions of the arrays, where each array is filtered to contain those elements which no array other than the current one contains

连接数组的版本，其中每个数组都被过滤以包含除了当前数组之外没有其他数组包含的那些元素

Then just write that down in JS:

然后用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
                ;
              }
            );
          }
        );
      }
    )
  );
}

Non-commented version, written more succinctly using ES6:

无注释版本，使用 ES6 编写更简洁：

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

回答by jpl1079

I came across this question in my research of the same coding challenge on FCC. I was able to solve it using forand whileloops, but had some trouble solving using the recommended Array.reduce(). After learning a ton about .reduceand other array methods, I thought I'd share my solutions as well.

我在研究 FCC 上的相同编码挑战时遇到了这个问题。我能够使用for和while循环解决它，但使用推荐的Array.reduce(). 在学习了大量关于.reduce数组和其他数组方法之后，我想我也会分享我的解决方案。

This is the first way I solved it, without using .reduce.

这是我解决它的第一种方法，不使用.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;
}

After learning and trying various method combinations, I came up with this that I think is pretty succinct and readable.

在学习并尝试了各种方法组合后，我想出了这个我认为非常简洁易读的方法。

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

}

That last .filterline I thought was pretty cool to dedup an array. I found it here, but modified it to use the 3rd callback parameter instead of the named array due to the method chaining.

最后.filter一行我认为对数组进行重复数据删除非常酷。我在这里找到了它，但由于方法链的原因，将其修改为使用第三个回调参数而不是命名数组。

This challenge was a lot of fun!

这个挑战非常有趣！

回答by kornieff

// 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]

回答by kornieff

Just use _.xoror copy lodash code.

只需使用_.xor或复制 lodash 代码。

回答by prnsml

Another simple, yet readable solution:

另一个简单但可读的解决方案：

 
/*
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]

Used functions: Array.prototype.filter()| Array.prototype.reduce()| Array.prototype.includes()

使用的函数： Array.prototype.filter()| Array.prototype.reduce()| Array.prototype.includes()

回答by Karan Jariwala

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
}

回答by vinayakj

Pure javascript solution.

纯javascript解决方案。

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"]

回答by Tim Reznich

My short solution. At the end, I removed duplicates by filter().

我的简短解决方案。最后，我通过 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]

回答by Angshuman Gupta

This is the JS code using higher order functions

这是使用高阶函数的JS代码

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

And it would return the output as: [3,5,4]

它会将输出返回为：[3,5,4]