2

I am working on an algorithm and trying to figure out how to solve it given the following information:

  1. I would like to find the intersection between n number of lists
  2. assume that I have a (properly working) intersection(a, b) function
  3. assume that the intersection() only takes two lists as input

So the problem would look something like this:

var a = {1, 2, 'b'}; 
var b = {2, 'b', 'b'};
var c = {2, 'b', 'c'};
var d = {'a', 'b', 'c'};

//this is the part that does not work, of course:
function intersect_all(d)
{
    //what goes in here???        
}

Note: I don't want to use python for this, since python has methods built into the lang that are not available for my app (or js, for that matter). I would like to solve it using the above information.

The result should look something like

{2, 'b'}

jml

jml
  • 1,745
  • 6
  • 29
  • 55
  • Besides some missing commas, I am a little confused by the first line of your example. The first array contains a reference to 'b' before it is defined. What did you intend here? – DaveGauer Apr 29 '11 at 20:57
  • 1
    possible duplicate of [Simplest code for array intersection in javascript](http://stackoverflow.com/questions/1885557/simplest-code-for-array-intersection-in-javascript) – epascarello Apr 29 '11 at 21:01
  • your code is very confused... is `b` inside `a` the same thing in `var b`? With `var c = [2, b, c];` you mean that `c` is a list that contains itself as an element? – 6502 Apr 29 '11 at 21:04
  • @epascarello: not a dupe at all. i specifically asked for the instersection of MORE THAN two lists. n lists, preferably. – jml Apr 29 '11 at 21:17

2 Answers2

4

Let's say you have an array of lists instead:

var lists = [];
lists[0] = [1, 2, 'b']; 
lists[1] = [2, 'b', 'b'];
lists[2] = [2, 'b', 'c'];
lists[3] = ['a', 'b', 'c'];

Then you can use this:

// say you call this passing the array of lists as the argument: intersect_all(lists)
function intersect_all(lists)
{
    if (lists.length == 0) return [];
    else if (lists.length == 1) return lists[0];

    var partialInt = lists[0];
    for (var i = 1; i < lists.length; i++)
    {
        partialInt = intersection(partialInt, lists[i]);
    }
    return partialInt;
}
lazycs
  • 1,586
  • 1
  • 13
  • 11
2

The ever useful underscore library has an intersect function, that takes multiple arrays.

http://documentcloud.github.com/underscore/#intersect

_.intersect([1, 2, 3], [101, 2, 1, 10], [2, 1]);
David
  • 8,340
  • 7
  • 49
  • 71