Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Intersection of multiple lists with IEnumerable.Intersect()

Tags:

c#

.net

linq

I have a list of lists which I want to find the intersection for like this:

var list1 = new List<int>() { 1, 2, 3 }; var list2 = new List<int>() { 2, 3, 4 }; var list3 = new List<int>() { 3, 4, 5 }; var listOfLists = new List<List<int>>() { list1, list2, list3 };  // expected intersection is List<int>() { 3 }; 

Is there some way to do this with IEnumerable.Intersect()?

EDIT: I should have been more clear on this: I really have a list of lists, I don't know how many there will be, the three lists above was just an example, what I have is actually an IEnumerable<IEnumerable<SomeClass>>

SOLUTION

Thanks for all great answers. It turned out there were four options for solving this: List+aggregate (@Marcel Gosselin), List+foreach (@JaredPar, @Gabe Moothart), HashSet+aggregate (@jesperll) and HashSet+foreach (@Tony the Pony). I did some performance testing on these solutions (varying number of lists, number of elements in each list and random number max size.

It turns out that for most situations the HashSet performs better than the List (except with large lists and small random number size, because of the nature of HashSet I guess.) I couldn't find any real difference between the foreach method and the aggregate method (the foreach method performs slightly better.)

To me, the aggregate method is really appealing (and I'm going with that as the accepted answer) but I wouldn't say it's the most readable solution.. Thanks again all!

like image 752
Oskar Avatar asked Nov 04 '09 15:11

Oskar


1 Answers

How about:

var intersection = listOfLists     .Skip(1)     .Aggregate(         new HashSet<T>(listOfLists.First()),         (h, e) => { h.IntersectWith(e); return h; }     ); 

That way it's optimized by using the same HashSet throughout and still in a single statement. Just make sure that the listOfLists always contains at least one list.

like image 130
Jesper Larsen-Ledet Avatar answered Oct 12 '22 15:10

Jesper Larsen-Ledet