Intersection of multiple lists with IEnumerable.Intersect()

Solution 1:

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.

Solution 2:

You can indeed use Intersect twice. However, I believe this will be more efficient:

HashSet<int> hashSet = new HashSet<int>(list1);
hashSet.IntersectWith(list2);
hashSet.IntersectWith(list3);
List<int> intersection = hashSet.ToList();

Not an issue with small sets of course, but if you have a lot of large sets it could be significant.

Basically Enumerable.Intersect needs to create a set on each call - if you know that you're going to be doing more set operations, you might as well keep that set around.

As ever, keep a close eye on performance vs readability - the method chaining of calling Intersect twice is very appealing.

EDIT: For the updated question:

public List<T> IntersectAll<T>(IEnumerable<IEnumerable<T>> lists)
{
    HashSet<T> hashSet = null;
    foreach (var list in lists)
    {
        if (hashSet == null)
        {
            hashSet = new HashSet<T>(list);
        }
        else
        {
            hashSet.IntersectWith(list);
        }
    }
    return hashSet == null ? new List<T>() : hashSet.ToList();
}

Or if you know it won't be empty, and that Skip will be relatively cheap:

public List<T> IntersectAll<T>(IEnumerable<IEnumerable<T>> lists)
{
    HashSet<T> hashSet = new HashSet<T>(lists.First());
    foreach (var list in lists.Skip(1))
    {
        hashSet.IntersectWith(list);
    }
    return hashSet.ToList();
}

Solution 3:

Try this, it works but I'd really like to get rid of the .ToList() in the aggregate.

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 };
var intersection = listOfLists.Aggregate((previousList, nextList) => previousList.Intersect(nextList).ToList());

Update:

Following comment from @pomber, it is possible to get rid of the ToList() inside the Aggregate call and move it outside to execute it only once. I did not test for performance whether previous code is faster than the new one. The change needed is to specify the generic type parameter of the Aggregate method on the last line like below:

var intersection = listOfLists.Aggregate<IEnumerable<int>>(
   (previousList, nextList) => previousList.Intersect(nextList)
   ).ToList();

Solution 4:

You could do the following

var result = list1.Intersect(list2).Intersect(list3).ToList();