Saturday, April 18, 2015

JavaScript: Removing Same Elements in an Array without Sorting It

Basic algorithm
For instance we have an object array: [10, 1, 1, 2, 1, 2]. Then we want to remove all the same occurrences to be just [10, 1, 2] without changing the original sequence.

Here's what I did. First of all, I used my fingers to imagine it. Then, I "translated" it to JavaScript.
  1. About the comparing (pairing), it uses combinatoric pattern.
    If you have 3 fruits and you wanna compare each of them, then you'll need 3 steps.
    If you have five fingers, then you'll need 10 steps to compare them all.
    Combination(total_number, 2)
    That's the basic idea.
    In this "translation", for instance that 3 fruits example, I created object of pairs. But not actually creating an object, just imaginary.
    As such:
    fruit 1 compared to fruit 1, fruit 2, and fruit 3.
    fruit 2 compared to fruit 1, fruit 2, and fruit 3.
    fruit 3 compared to fruit 1, fruit 2, and fruit 3.
    As you can see, there are repetitions.
    Without conditional statement, it will compare to itself and everything'll be broken.
    You can read about that below, about the if statement.
  2. About the array manipulation, I use splice(index, how_many, elm_1, ..., elm_n) method to remove the element.
    And to keep the first element (the comparison reference) intact and only the next occurrence gets deleted, I put less than operator. The first index (denoted by i or m in the script below) is the array element reference, and the next one (denoted by j or n) is the other element besides that reference element.
  3. The array reconstruction has stages, so I put "flag" to indicate whether it should re-invoke itself or not. The "stages" occur because whenever an array element gets deleted, the length of the array will change, thus the index shifting.
  4. This function won't change the original array because it uses slice() method to clone it first.

This can be copied then paste it directly to your browser console or script editor, run it (hit enter/return), and observe the output.
Updated April 19, 2015

var filtered_array = r_d(your_original_array);

The shorter version at GitHub
In that shorter version, instead of completely deleting the array element, I substitute it with "array_element (*)" string. You can put other type of dummy element so that it won't mix with the actual array elements.

Different version at GitHub
In this version, I use the actual Object dilly. It's one line shorter than the shortened version of the 1st snippet.
This object construction method will return the sorted array. So you probably do not want to use this version.
But if... Hm.
That is all.

No comments:

Post a Comment

Tell me what you think...