Algorithm Symmetric Difference

Algorithm Symmetric Difference

🚩 Remember to use Read-Search-Ask if you get stuck. Try to pair program 👥 and write your own code 📝

🏁 Problem Explanation:

Symmetric difference is the difference between two sets i.e., the collection of elements which are members of either set but not both.

In the symmetric difference algorithm, you would work through the arrays of numbers in this manner: sym(A, B, C) translates to sym(sym(A, B), C) i.e., the symmetric difference of set A and set B is found first and then, the symmetric difference of the resultant set and set C is found.

Example: sym([1, 2, 5], [2, 3, 5], [3, 4, 5]) equals [1, 4, 5].

Relevant Links

• YouTube - Symmetric difference
• Symmetric difference
• JS Object
• JS Arguments
• JS Array Prototype Reduce
• JS Reduce Made Easy

💬 Hint: 1

The arguments object is not an array. It is similar to an array, but does not have any array properties except length. For example, it does not have the pop method. However, it can be converted to a real array: var args = Array.prototype.slice.call(arguments);

try to solve the problem now

💬 Hint: 1

Write a function that returns the symmetric difference of the two arrays: yourFunction([1, 2, 3], [2, 4, 6]) must return [1, 3, 4, 6]

try to solve the problem now

💬 Hint: 1

Use Array.prototype.reduce along with yourFunction to repeat the process on multiple arguments

Something strange about the definition of symmetric difference is that if one identical item occurs in three different sets, it is a member of the symmetric difference. For example:

a = [1, 2, 5]
b = [2, 3, 5]
c = [3, 4, 5]

sym(a, b) = [1, 3]
sym([1, 3], c) = [1, 4, 5]

try to solve the problem now

Spoiler Alert!

Solution ahead!

🔰 Basic Code Solution:

function sym() {
    var args = [];
    for (var i = 0; i < arguments.length; i++) {
        args.push(arguments[i]);
    }

    function symDiff(arrayOne, arrayTwo) {
        var result = [];

        arrayOne.forEach(function(item) {
            if (arrayTwo.indexOf(item) < 0 && result.indexOf(item) < 0) {
                result.push(item);
            }
        });

        arrayTwo.forEach(function(item) {
            if (arrayOne.indexOf(item) < 0 && result.indexOf(item) < 0) {
                result.push(item);
            }
        });

        return result;
    }

    // Apply reduce method to args array, using the symDiff function
    return args.reduce(symDiff);
}

🚀 Run Code

Code Explanation:

• push() is used to break down the arguments object to an array, args.
• The symDiff function finds the symmetric difference between two sets. It is used as a callback function for the reduce() method called on args.
• arrayOne.forEach() pushes the elements to result which are present only in arrayOne as well as not already a part of result.
• arrayTwo.forEach() pushes the elements to result which are present only in arrayTwo as well as not already a part of result.
• The result, which is the symmetric difference is returned. This solution works for any number of sets.

Relevant Links

• JS For Loops Explained
• array.length
• JS Array Prototype Push
• JS Array Prototype ForEach
• JS Array Prototype IndexOf

🌻 Intermediate Code Solution:

function sym() {

  // Convert the argument object into a proper array
  var args = Array.prototype.slice.call(arguments);

  // Return the symmetric difference of 2 arrays
  var getDiff = function(arr1, arr2) {

    // Returns items in arr1 that don't exist in arr2
    function filterFunction(arr1, arr2) {
      return arr1.filter(function(item) {
        return arr2.indexOf(item) === -1;
      });
    }

    // Run filter function on each array against the other
    return filterFunction(arr1, arr2)
      .concat(filterFunction(arr2, arr1));
  };

  // Reduce all arguments getting the difference of them
  var symarray = args.reduce(getDiff, []);

  // Run filter function to get the unique values
  var unique = symarray.filter(function(elem, index, self) {
    return index === self.indexOf(elem);
    });
  return unique;
}

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

🚀 Run Code

Code Explanation:

• The slice() method is used to break down the arguments object to an array, args.
• The getDiff function finds the symmetric difference between two sets, arr1 and arr2. It is used as a callback function for the reduce() method called on args.
• The first filterFunction() returns elements in arr1 that don't exist in arr2.
• The next filterFunction() is run on each array against the other to check the inverse of the first check for uniqueness and concatenate it.
• symarray consists of the reduced arguments.
• filter() is used on symarray to keep only the unique values and unique is returned.

Relevant Links

• JS Array Prototype Slice
• JS Array Prototype Filter
• JS Array Prototype Concat

🚨 Advanced Code Solution:

function sym() {
  // difference between set A and set B
  const diff = (A, B) => new Set([...A].filter(n => !B.has(n)));
  // spread operator to convert array like object to array
  const result = [...arguments]
    // map elements in arguments (array) to Set
    .map(arr => new Set(arr))
    // using the formula in https://en.wikipedia.org/wiki/Symmetric_difference
    // i reduce it by uniting the diff(A, B) and diff(B, A)
    .reduce((acc, set) => new Set([...diff(acc, set), ...diff(set, acc)]));

  // convert the set to array by using spread operator again
  return [...result];
}

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

🚀 Run Code

Code Explanation:

• diff consists of the difference between set A and set B.
• result holds the object which has been converted to an array using the spread operator.
• map() is used to populate the new set object with elements from arr using the symmetric difference formula.
• Before returning, the set is converted to an array using the spread operator.

Relevant Links

• Set object
• Set.prototype.has()
• Spread operator
• JS Array Prototype Map
• Map.prototype.has()

🏆 Credits:

If you found this page useful, you may say thanks to the contributors by copying and pasting the following line in the main chat:

Thanks @Rafase282 @imranismail @dakshshah96 for your help with Algorithm: Symmetric Difference

📋 NOTES FOR CONTRIBUTIONS:

• ⚠️ DO NOT add solutions that are similar to any existing solutions. If you think it is similar but better, then try to merge (or replace) the existing similar solution.
• Add an explanation of your solution.
• Categorize the solution in one of the following categories — Basic, Intermediate and Advanced. 🚥
• Please add your username only if you have added any relevant main contents. (:warning: DO NOT remove any existing usernames)

See 👉 Wiki Challenge Solution Template for reference.