intersection of n lists via JS
I am working on an algorithm and trying to figure out how to solve it given the following information:
- I would like to find the intersection between n number of lists
- assume that I have a (properly working) intersection(a, b) function
- 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开发者_StackOverflow 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
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;
}
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]);
精彩评论