Intersection of Dictionary>

Question

public class A
{
    public double K {get; set;}
    and other fields in here
}

I have a Dictionary of List<A> indexed by Datetime,

Dictionary<System.Datetime, List<A>>;

How do I get the intersection of all the List<A>, returned again as a Dictionary<System.Datetime, List<A>>? Intersection meaning the largest List<A> that such that each Datetime contains that A.K.

I can do it with for loops. But I am looking for a performant elegant solution in Linq.

{'5-19-2015', List<20, 25, 27, 30> 
 '6-10-2015', List<20, 25, 27, 28>
 '9-5-2015', List<20, 21, 22, 23, 24, 25, 26,27,28,29,30}

Would return

 {'5-19-2015', List<20, 25, 27> 
 '6-10-2015', List<20, 25, 27>
 '9-5-2015', List<20, 25, 27>}

EDIT 1

As per the suggestion below, I tried this but it doesn't work

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TestLinq
{


public class A : IComparable, IEquatable<A>
{
    public double K { get; set; }

    public int CompareTo(object obj)
    {
        A other = (A)obj;

        if (this.K > other.K)
            return 1;
        if (this.K < other.K)
            return -1;

        return 0;
    }

    public bool Equals(A other)
    {
        return this.K == other.K;
    }
}

    class Program
    {
        static void Main(string[] args)
        {
            Dictionary<DateTime, List<A>> dict = new Dictionary<DateTime, List<A>> {
                { DateTime.Now, new List<A> {
                    new A { K = 20 }, new A { K = 25 }, new A { K = 27 }, new A { K= 30 } } },
                { DateTime.Now.AddDays(1),  new List<A> {
                    new A { K = 20 }, new A { K = 25 }, new A { K = 27 }, new A { K = 28 } } },
                { DateTime.Now.AddDays(2), new List<A> {
                    new A { K = 20 }, new A { K = 21 }, new A { K = 22 }, new A { K = 23 }, new A { K = 24 },
                    new A { K= 25 }, new A {K=  26 }, new A { K=27 }, new A {K= 28 }, new A { K=29 }, new A { K =30 } }
                }};

            var intersectedList = dict.Values.Skip(1)
                .Aggregate(
                    new HashSet<A>(dict.Values.First()),
                    (h, e) => { h.IntersectWith(e); return h; }
                );

            Console.ReadLine();
        }
    }
}

Please add the "for loop" code. Community can direct you then. — Karthik AMR, Mar 22 '17 at 04:30
All the List whose K are the same across Datetime is what I mean by intersection. — Ivan, Mar 22 '17 at 04:31

score 1 · Answer 1 · answered Mar 22 '17 at 05:13

1

Your sample code represents Dictionary<DateTime, List<double>>, if so check whether the below code is helpful for you or not.

Dictionary<DateTime, List<double>> dict = new Dictionary<DateTime, List<double>> {
{ DateTime.Now, new List<double> { 20, 25, 27, 30 } },                
{ DateTime.Now.AddDays(1), new List<double> { 20, 25, 27, 28 } },                
{ DateTime.Now.AddDays(2), new List<double> { 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 }
}};

var intersectedList = dict.Values.Skip(1)
    .Aggregate(
        new HashSet<double>(dict.Values.First()),
        (h, e) => { h.IntersectWith(e); return h; }
    );

It will return you an intersected list with 20, 25 and, 27.

answered Mar 22 '17 at 05:13

Karthik AMR

1,694
21
29

@Ivan you should check out this one - http://stackoverflow.com/questions/1674742/intersection-of-multiple-lists-with-ienumerable-intersect – Karthik AMR Mar 22 '17 at 05:18
Thanks that is very close. What if instead of List it is List. See original post. I just said double to make it easier to type. I couldn't make your code work then. – Ivan Mar 22 '17 at 05:39
I have a feeling IComparable is not working in my case. How do I pass the actual fields I want to compare of A in your code? – Ivan Mar 22 '17 at 05:41
Or more accurately, operator== – Ivan Mar 22 '17 at 05:48
see Edit 1 above. – Ivan Mar 22 '17 at 15:05

score 0 · Accepted Answer · answered Mar 22 '17 at 16:03

I gave credit where credit is due to Karthik, but in order to help the next person, here is what I needed to do. First, notice that I added the Name property so that when I am debugging, I could tell which A I was looking at. I also added IntersectAll to showcase a different approach that is more readable. They both work.

Note that you must implement IComparable, IEquatable<A>, GetHashCode, CompareTo, and Equals.

There is a greater issue of how to implement these things because in one instance, if your class A is more complicated (has more properties) and has different needs for what it means for two objects to be equal can be at odds with each other.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TestLinq
{
    public class A : IComparable, IEquatable<A>
    {
        public string Name { get; set; }
        public double K { get; set; }

        public override int GetHashCode()
        {
            return K.GetHashCode();
        }

        public int CompareTo(object obj)
        {
            A other = (A)obj;

            if (this.K > other.K)
                return 1;
            if (this.K < other.K)
                return -1;

            return 0;
        }

        public bool Equals(A other)
        {
            return this.K == other.K;
        }
    }

    class Program
    {
        static 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();
        }

        static void Main(string[] args)
        {
            Dictionary<DateTime, List<A>> dict = new Dictionary<DateTime, List<A>> {
                { DateTime.Now, new List<A> {
                    new A { Name = "1", K = 20 }, new A {  Name = "1", K = 25 }, new A { Name = "1", K = 27 }, new A {  Name = "1", K= 30 } } },
                { DateTime.Now.AddDays(1),  new List<A> {
                    new A {  Name = "2",K = 20 }, new A { Name = "2", K = 25 }, new A { Name = "2", K = 27 }, new A { Name = "2", K = 28 } } },
                { DateTime.Now.AddDays(2), new List<A> {
                    new A { Name = "3", K = 20 }, new A {  Name = "3",K = 21 }, new A { Name = "3", K = 22 },
                    new A { Name = "3", K = 23 }, new A {  Name = "3",K = 24 },
                    new A { Name = "3", K= 25 }, new A { Name = "3",K=  26 }, new A {  Name = "3",K=27 },
                    new A { Name = "3", K= 28 }, new A { Name = "3", K=29 }, new A { Name = "3", K =30 } }
                }};

#if true
            var intersectedList = dict.Values.Skip(1)
                .Aggregate(
                    new HashSet<A>(dict.Values.First()),
                    (h, e) => { h.IntersectWith(e); return h; }
                );
#else
            var intersectList = IntersectAll( dict.Values);
#endif
            Console.ReadLine();
        }
    }
}

Intersection of Dictionary>

2 Answers2