How to Find the Intersection of Multiple Lists

God breathing through me

How to Find the Intersection of Multiple Lists

Published on August 29, 2008

Recently I ran in a situation where I had to get the intersection of multiple generic lists in order to filter my final result. I know that there are several approaches to work around this but I was interested to apply the new Intersect extension method in .NET 3.5 and extend it for multiple lists.

I can remember the university days when we had to extend a proven theorem for two objects to N objects and this was somehow similar to that!

Here I just want to share a code snippet that I used to accomplish this goal. This is easy to adapt for any application since the core implementation follows a simple pattern.

Suppose that you have a class called Person with a few properties as you see below. I intentionally used that ID property in order to make it easier for myself to distinguish two Person instances when I want to compare them. However, you may need to do some extra work for your comparison if there isn’t such an identifier for your entities.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace MultipleIntersectionSample
{
    public class Person
    {
        #region Properties
 
        public int ID { get; set; }
 
        public string Name { get; set; }
 
        #endregion
 
        #region Public Constructor
 
        public Person()
        {
        }
 
        public Person(int id, string name)
        {
            this.ID = id;
            this.Name = name;
        }
 
        #endregion
    }
}

Also suppose that I have a list of multiple lists of Person objects and I want to find the intersection of all these lists. Here is a code that shows three lists of Person objects and there is a container list of all these lists. I want to find the intersection of all the lists in containerList.

static void Main(string[] args)
{
    Console.Title = "How to Find the Intersection of Multiple Lists";
 
    List<List<Person>> containerList = new List<List<Person>>();
 
    List<Person> list1 = new List<Person>();
    list1.Add(new Person(1, "Keyvan Nayyeri"));
    list1.Add(new Person(2, "Simone Chiaretta"));
    list1.Add(new Person(3, "Phil Haack"));
    containerList.Add(list1);
 
    List<Person> list2 = new List<Person>();
    list2.Add(new Person(1, "Keyvan Nayyeri"));
    list1.Add(new Person(2, "Simone Chiaretta"));
    list2.Add(new Person(4, "Scott Hanselman"));
    containerList.Add(list2);
 
    List<Person> list3 = new List<Person>();
    list3.Add(new Person(1, "Keyvan Nayyeri"));
    list3.Add(new Person(2, "Simone Chiaretta"));
    list3.Add(new Person(3, "Phil Haack"));
    list3.Add(new Person(5, "Scott Guthrie"));
    containerList.Add(list3);
 
    // TODO: Find the intersection or go home!
 
    Console.ReadLine();
}

There are several approaches to find this intersection but I want to use the Intersect extension method in .NET 3.5. One basic requirement of this method is the existence of an IEqualityComparer object that will be used to compare two objects of a type for their equality. You need to write your own logic for this comparison by implementing the IEqualityComparer generic interface for your own type. For example, I should implement IEqualityComparer<Person> as you see here:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace MultipleIntersectionSample
{
    class PersonEqualityComparer : IEqualityComparer<Person>
    {
        #region IEqualityComparer<Person> Members
 
        public bool Equals(Person x, Person y)
        {
            if (x.ID != y.ID)
                return false;
            else
                return true;
        }
 
        public int GetHashCode(Person obj)
        {
            return base.GetHashCode();
        }
 
        #endregion
    }
}

Here you notice the reason why I chose that ID property for my Person class to simply compare my objects!

Having this comparer, I can write a function that gets my containerList and returns a list of Person objects that is equal to my desire intersection.

The logic is simple: I get a temporary list and iterate through all the lists. On each iteration I get the intersection of the current list with my last intersection (that is hold into the temp list). After finishing the loop, I have my intersection in the temporary list.

private static List<Person> GetIntersection(List<List<Person>> containerList)
{
    IEnumerable<Person> tempList = containerList[0];
 
    PersonEqualityComparer comparer = new PersonEqualityComparer();
 
    foreach (List<Person> list in containerList)
    {
        tempList = tempList.Intersect<Person>(list, comparer);
    }
 
    return tempList.ToList<Person>();
}

Alright! Now I just need to apply this function and display my intersection.

static void Main(string[] args)
{
    Console.Title = "How to Find the Intersection of Multiple Lists";
 
    List<List<Person>> containerList = new List<List<Person>>();
 
    List<Person> list1 = new List<Person>();
    list1.Add(new Person(1, "Keyvan Nayyeri"));
    list1.Add(new Person(2, "Simone Chiaretta"));
    list1.Add(new Person(3, "Phil Haack"));
    containerList.Add(list1);
 
    List<Person> list2 = new List<Person>();
    list2.Add(new Person(1, "Keyvan Nayyeri"));
    list2.Add(new Person(2, "Simone Chiaretta"));
    list2.Add(new Person(4, "Scott Hanselman"));
    containerList.Add(list2);
 
    List<Person> list3 = new List<Person>();
    list3.Add(new Person(1, "Keyvan Nayyeri"));
    list3.Add(new Person(2, "Simone Chiaretta"));
    list3.Add(new Person(3, "Phil Haack"));
    list3.Add(new Person(5, "Scott Guthrie"));
    containerList.Add(list3);
 
    foreach (Person person in GetIntersection(containerList))
    {
        Console.WriteLine(string.Format("ID: {0} - Name: {1}",
            person.ID.ToString(), person.Name));
    }
 
    Console.ReadLine();
}

As always, you can download the source code sample.

10 Comments

Simone
Aug 29, 2008 2:30 AM
#

Ahah.. Great example :)

Keyvan Nayyeri
Aug 29, 2008 3:12 AM
#

@Simone:

For its sample names or its nature?! ;-)

ins0mniaque
Aug 29, 2008 4:09 AM
#

One-liner : containerList.Aggregate ( ( a, b ) => a.Intersect ( b, new PersonEqualityComparer() ) )

And if you still intend to put it in a function, you should yield return the results...

ins0mniaque
Aug 29, 2008 4:38 AM
#

I'm too tired... ;)

Stratch that yield thing, just make the return type IEnumerable < Person > and directly return the query, to avoid creating a list with ToList ( ).

Keyvan Nayyeri
Aug 29, 2008 6:09 AM
#

@ins0mniaque:

Looks like that you're drunk! You're not tired!

Dew Drop - August 29, 2008 | Alvin Ashcraft's Morning Dew
Aug 29, 2008 8:02 AM
#

Pingback from Dew Drop - August 29, 2008 | Alvin Ashcraft's Morning Dew

µilad
Aug 30, 2008 3:26 PM
#

Nice!

Keyvan would you plz post something about running a scheduled task in as ASP.NET Application. Like sending a daily email or sth.

Keyvan Nayyeri
Aug 30, 2008 9:01 PM
#

@Milad:

What's your problem? Have you checked our Abidar task scheduler system for the ASP.NET:

nayyeri.net/.../how-to-build-a- nayyeri.net/.../how-to-build-a- nayyeri.net/.../abidar-ndash-as http://www.codeplex.com/abidar nayyeri.net/.../abidar-1.0-beta

Link Listing - August 30, 2008
Aug 31, 2008 12:40 AM
#

Link Listing - August 30, 2008

LordHits
Feb 23, 2010 6:53 PM
#

A more efficient solution:

http://stackoverflow.com/questions/1674742/intersection-of-multiple-lists-with-ienumerable-intersect/1674917

Keyvan Nayyeri

Recent Posts

Archive

How to Find the Intersection of Multiple Lists

Leave a Comment