Skip to main content

JavaScript Function For Symmetric Difference

EDIT: Note that the code below works (at least as far as I know) so long as you assume each array is formatted like a set.  If either of the arrays have repeating entries -- i.e. behave the way arrays are allowed to behave -- the algorithm won't work and is seriously in error.  Oh well -- back to the drawing board.

The symmetric difference of two sets is the difference between their union and their intersection. Consider the following sets:
A = {1, 2, 3, 4, 5}
B = {1, 3, 5, 7, 9} 
The union of A and B is
{1, 2, 3, 4, 5, 7, 9}.
The intersection of A and B is
{1, 3, 5}.
So the symmetric difference of A and B is
{1, 2, 3, 4, 5, 7, 9} - {1, 3, 5} = {2, 4, 7, 9}.
My job was to construct a two argument JavaScript function that would correctly return this result.  I decided to proceed as follows:
1. Concatenate the two arrays to produce their "union" (with duplicate values).
2. Remove any value that has a duplicate.
Here is my code:
function diffArray(arr1, arr2) {
  var newArr = arr1.concat(arr2);
  newArr = newArr.filter(function (value, index, array) {
                elOut = array.slice(0,index).concat(array.slice(index+1,array.length));
  return elOut.indexOf(value) == -1;
                });
  return newArr;
}
The function diffArray() takes two arrays as arguments (no debugging for non-array inputs).  It concatenates them together as newArr.  Then it runs newArr through the function filter().  From what I can tell, this function is going through each element of the newArr and returning it if and only if it passes a Boolean test.  Calling the function accordingly gives me three variables to work with: the index of the array being examined, the value of that index, and the array itself.

So what I wanted to do was consider whether, for a given item in the array, a duplicate of that item was present in the array.  Using the method indexOf(), I knew I could search an array and get the position of a given value.  The problem was that I needed the index of the duplicate of the value I was searching for and not the value itself -- searching in newArr wouldn't work.  The solution was to take the value I was searching for out of the array.  To do so, I sliced the array on the index of that value, forming a new array, elOut ("Get the element out!")  I then had the callback return False (-1) if the value was still present in elOut.  Reconstructing newArr to include only those elements that passed the test, I was then able to fulfill the requirements of the assignment.

Comments

Post a Comment

Popular posts from this blog

Getting Geodata From Google's API

The apps I'm going to be analyzing are part of Dr. Charles Severance's MOOC on Python and Databases and work together according to the following structure (which applies both in this specific case and more generally to any application that creates and interprets a database using online data). The data source, in this case, is Google's Google Maps Geocoding API.  The "package" has two components: geoload.py  and geodump.py .  geoload.py  reads a list of locations from a file -- addresses for which we would like geographical information -- requests information about them from Google, and stores the information on a database ( geodata.db ).  geodump.py  reads and parses data from the database in JSON, then loads that into a javascript file.  The javascript is then used to create a web page on which the data is visualized as a series of points on the world-map.  Dr. Severance's course focuses on Python, so I'm only going to work my way through ...
Post a Comment
Read more

Shell Sort

Today I spent a little bit of time researching the "Shell" sort.  I wanted to post a few notes about the Princeton Algorithms Course's implementation to help me solidify my understanding. First, a little tidbit.  When I first heard about this algorithm, I thought it had something to do with shell games.  Turns out a man named Donald Shell discovered this method of sorting, whence the name. The Algorithms  book gives the following explanation (Sedgewick and Wayne,  Algorithms, 4th ed., p. 258): The idea is to rearrange the array to give it the property that taking every hth entry (starting anywhere) yields a sorted subsequence. Such an array is said to be h-sorted. Put another way, an h-sorted array is h independent sorted subsequences, interleaved together. By h-sorting for some large values of h, we can move items in the array long distances and thus make it easier to h-sort for smaller values of h. Using such a procedure for any sequence of values o...
Post a Comment
Read more

It's a Date

I guess I should really be putting these things up in GitHub.  The way I see it, the coding journal is just a place to share the code I write or study along with any notes I have about it.  It's sort of a documentation LiveJournal, if you will. Anyway, this is a "study" for my project idea: create an app that will prompt the user for two dates, then calculate the difference between them. The burden of this study is twofold: (1) convert dates in standard American form (e.g. December 15, 1993) into dates in standard American numeric form (e.g. 12/15/1993); (2) create a numerical representation of the date. To process the date, I started with a list of the months.  I then used a loop to create a dictionary that would attach a value to each month. Next I had to parse the user entry (I haven't added any debugging for incorrect entries yet). I did so by splitting the entry into "raw" data.  I used my dictionary to process the month name into a number, str...
Post a Comment
Read more