0

I am a javascript newbie so bear with me. I have lists as so:

var list1 = ['a','b','c'];
var list2 = ['c','d','e'];
var list3 = ['f','g'];

As you see, list1 and list2 intersect at 'c' while list3 is disjoint from both list1 and list2.
The result should be

['a','b','c','d','e'],['f','g'] // Two arrays

We have combined list1 and list2 since they intersect while leaving list3 as is. Another example:

var list1 = ['a','b','c'];
var list2 = ['d','e','f'];
var list3 = ['f','g','a'];

Here we see list1 and list2 don't intersect, list1 intersects with list3 at 'a' and list2 intersects list3 at 'f'. So since all 3 intersect, the result returned would be:

['a','b','c','d','e','f','g'] // One array

Any help is appreciated
KA

PS: I did search the site for a similar problem and I came across one intersection of n lists via JS Its similar but doesn't serve my use case.

Community
  • 1
  • 1
Karan Ashar
  • 1,392
  • 1
  • 10
  • 23

2 Answers2

1

If you have two-list intersection and union functions, you can get what you want with this logic:

var lists; // initialized with the lists you want to process
var merged = [];
for each list a in lists {
    for each list b in merged {
        if intersect(a,b) != empty {
            remove b from merged;
            a = union(a,b);
        }
    }
    add a to merged;
}

You just have to be a little careful about removing b from merged while you are looping through all the elements of merged. It might be simpler to iterate through merged from the last to the first element. The underscore library is a nice place to find functions for intersection and union.

Ted Hopp
  • 232,168
  • 48
  • 399
  • 521
  • I tried your sudo code on paper and it seems to work ! No way my little mind would have processed this :) One thing I didn't understand was your concern about removing b from merged and iterating from last to first on merged. Could you explain? Thumbs up for the pseudo code though (Tried to do this but don't have enough reputation :( ). – Karan Ashar Aug 28 '11 at 01:45
  • Say that you're looping through `merged` by incrementing an index `i` and you need to remove element `b` (which is at position `i`). Typically, you'd do this by moving the last element of `merged` to `i` and shorten the list length by one. If you increment `i` in the same pass through the loop, then you will have skipped testing the element that had been last (and is now where `b` used to be). Starting at the end and decrementing the index avoids this problem. – Ted Hopp Aug 28 '11 at 06:27
  • I tried out the pseudo code today and it works perfect ! Thanks Ted. – Karan Ashar Aug 29 '11 at 01:20
0

try

<script>
    Array.prototype.unique = function() {  
        var temp = {}, len = this.length;
        for(var i=0; i < len; i++)  {  
            if(typeof temp[this[i]] == "undefined") {
                temp[this[i]] = 1;
            }  
        }  
        this.length = 0;
        len = 0;
        for(var i in temp) {  
            this[len++] = i;
        }  
        return this;  
    }  

    var list1 = ['a','b','c'];
    var list2 = ['c','d','e'];
    var list3 = ['f','g'];


    start = new Date().getTime(); 
    var list = list1.concat(list2).concat(list3).unique(); 
</script>
shenhengbin
  • 4,236
  • 1
  • 24
  • 33