Juan - 1 year ago 64
Javascript Question

# Recursive function for symmetric difference

i made a function to calculate de symmetric difference between arrays passed as arguments. I did it for two arrays and it worked. The problem now is that i want to extend the function to n variables. I think that i should calculate the symm difference if the arguments.length of the function is equal to two, else i should call a recursive function to calculate the symm diff between the other elements and the first two ? I don't know, i'm very confused.

``````function sym(args) {

var arr=[].slice.call(arguments);
var cnts={};
var result=[];

if(arguments.length==2){

arr=arguments[0].concat(arguments[1]);
console.log(arr);
for(var number in arr){

if(cnts.hasOwnProperty(arr[number])){

++cnts[arr[number]].cnt;

}

else   cnts[arr[number]]={cnt:1,val:arr[number]};

}

for(var counts in cnts){

if(cnts[counts].cnt===1) result.push(cnts[counts].val);

}

}

else{

var first=arguments[0];
var nextDiff=function(next){

return ...........?????????;

};

}

return result;
}

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

There are two key insights here. The first is that we have

``````sym_diff(A1, A2, ..., An) === sym_diff(sym_diff(A1, A2), A3, ..., An)
``````

This follows from the fact that symmetric difference is associative and allows us to recur.

The second is that

``````sym_diff(A, B) === diff(A, B) ++ diff(B, A)
``````

where `++` here means union and `diff` is the usual relative difference.

Hence:

``````function sym_diff() {
// Convert the passed arguments to an array for convenience
let args = Array.prototype.slice.call(arguments);

// This is an example of an immediately-invoked function expression
// (IIFE). Basically, we define a function and then immediately call it (see * below)
// in one go and return the result

return (function sym_diff(a, b) {
// a: the first argument
// b: an array containing the rest of the arguments

if (!b.length) {
// If only a is given, return a if is an array, undefined otherwise
return Array.isArray(a) ? a : undefined;
}
else if (b.length === 1) {
// Define a function that takes two arrays s and t, and returns
// those elements of s that are not in t
let diff = (s, t) => s.filter(i => t.indexOf(i) === -1);

// Use the second insight to compute the sym_diff of a and
// b[0]
return diff(a, b[0]).concat(diff(b[0], a));
}
else {
// Use the first insight to recursively compute the sym_diff
// We pass [b[0]] because sym_diff expects an array of arrays
// b.slice(1) gives all of b except the first element
return sym_diff(sym_diff(a, [b[0]]), b.slice(1));
}
})(args[0], args.slice(1)); //* Here is where we pass the arguments to the IIFE
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download