How to Find the Intersection of Multiple Lists : CSharp Feeds

How to Find the Intersection of Multiple Lists

by Keyvan Nayyeri via Keyvan Nayyeri on 8/29/2008 5:06:48 AM

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();
}