Przecięcie wielu list za pomocą IEnumerable.Intersect ()

Mam listę list, dla których chcę znaleźć skrzyżowanie w ten sposób:

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

Czy istnieje sposób, aby to zrobić za pomocą IEnumerable.Intersect ()?

EDYCJA: Powinienem był być bardziej jasny: naprawdę mam listę list, nie wiem, ile będzie, trzy powyższe listy to tylko przykład, to, co mam, to tak naprawdę IEnumerable<IEnumerable<SomeClass>>

ROZWIĄZANIE

Dzięki za wszystkie świetne odpowiedzi. Okazało się, że istnieją cztery opcje rozwiązania tego problemu: Lista + agregacja (@Marcel Gosselin), Lista + foreach (@JaredPar, @Gabe Moothart), HashSet + agregat (@jesperll) i HashSet + foreach (@Tony the Pony). Przeprowadziłem testy wydajnościowe na tych rozwiązaniach (różna liczba list , liczba elementów na każdej liście i maksymalny rozmiar liczby losowej .

Okazuje się, że w większości sytuacji HashSet działa lepiej niż List (z wyjątkiem dużych list i małego rozmiaru liczb losowych, ze względu na naturę HashSet). Nie mogłem znaleźć żadnej rzeczywistej różnicy między metodą foreach a agregatem metoda (każda metoda działa nieco lepiej).

Dla mnie metoda agregacji jest naprawdę atrakcyjna (i wybieram to jako akceptowaną odpowiedź), ale nie powiedziałbym, że jest to najbardziej czytelne rozwiązanie. Jeszcze raz dziękuję wszystkim!

Co powiesz na:

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

W ten sposób jest zoptymalizowany przy użyciu tego samego HashSet w całym tekście i nadal w jednej instrukcji. Upewnij się tylko, że listOfLists zawsze zawiera przynajmniej jedną listę.

Rzeczywiście możesz użyć Intersectdwa razy. Uważam jednak, że będzie to bardziej wydajne:

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

Oczywiście nie ma problemu z małymi zestawami, ale jeśli masz wiele dużych zestawów, może to być znaczące.

Zasadniczo Enumerable.Intersectmusi tworzyć zestaw dla każdego połączenia - jeśli wiesz, że będziesz wykonywać więcej operacji na zestawach, równie dobrze możesz go zachować.

Jak zawsze, miej oko na wydajność i czytelność - metoda łączenia w łańcuch dwóch połączeń Intersectjest bardzo atrakcyjna.

EDYCJA: W przypadku zaktualizowanego pytania:

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

Lub jeśli wiesz, że nie będzie pusty, a Skip będzie stosunkowo tani:

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

Spróbuj tego, to działa, ale naprawdę chciałbym pozbyć się .ToList () w agregacji.

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

Aktualizacja:

Po komentarzu @pomber można pozbyć się wywołania ToList()wewnętrznego Aggregatei przenieść go na zewnątrz, aby wykonać je tylko raz. Nie testowałem wydajności, czy poprzedni kod jest szybszy od nowego. Potrzebna zmiana polega na określeniu parametru typu generycznego Aggregatemetody w ostatnim wierszu, jak poniżej:

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

Możesz wykonać następujące czynności

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

To jest moja wersja rozwiązania z metodą rozszerzenia, którą nazwałem IntersectMany.

public static IEnumerable<TResult> IntersectMany<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, IEnumerable<TResult>> selector)
{
    using (var enumerator = source.GetEnumerator())
    {
        if(!enumerator.MoveNext())
            return new TResult[0];

        var ret = selector(enumerator.Current);

        while (enumerator.MoveNext())
        {
            ret = ret.Intersect(selector(enumerator.Current));
        }

        return ret;
    }
}

Więc użycie wyglądałoby mniej więcej tak:

var intersection = (new[] { list1, list2, list3 }).IntersectMany(l => l).ToList();

To jest moje jednorzędowe rozwiązanie dla List of List (ListOfLists) bez funkcji intersect:

var intersect = ListOfLists.SelectMany(x=>x).Distinct().Where(w=> ListOfLists.TrueForAll(t=>t.Contains(w))).ToList()

To powinno działać dla .net 4 (lub nowszego)

Po przeszukaniu sieci i nie wymyśleniu czegoś, co mi się podobało (lub co zadziałało), spałem na tym i wymyśliłem to. Mój używa klasy ( SearchResult), która ma EmployeeIdw sobie i to jest rzecz, która musi być wspólna dla wszystkich list. Zwracam wszystkie rekordy, które mają na EmployeeIdkażdej liście. To nie jest wyszukane, ale jest proste i łatwe do zrozumienia, po prostu to, co lubię. W przypadku małych list (w moim przypadku) powinno to działać dobrze - i każdy może to zrozumieć!

private List<SearchResult> GetFinalSearchResults(IEnumerable<IEnumerable<SearchResult>> lists)
{
    Dictionary<int, SearchResult> oldList = new Dictionary<int, SearchResult>();
    Dictionary<int, SearchResult> newList = new Dictionary<int, SearchResult>();

    oldList = lists.First().ToDictionary(x => x.EmployeeId, x => x);

    foreach (List<SearchResult> list in lists.Skip(1))
    {
        foreach (SearchResult emp in list)
        {
            if (oldList.Keys.Contains(emp.EmployeeId))
            {
                newList.Add(emp.EmployeeId, emp);
            }
        }

        oldList = new Dictionary<int, SearchResult>(newList);
        newList.Clear();
    }

    return oldList.Values.ToList();
}

Oto przykład użycia listy int, a nie klasy (to była moja oryginalna implementacja).

static List<int> FindCommon(List<List<int>> items)
{
    Dictionary<int, int> oldList = new Dictionary<int, int>();
    Dictionary<int, int> newList = new Dictionary<int, int>();

    oldList = items[0].ToDictionary(x => x, x => x);

    foreach (List<int> list in items.Skip(1))
    {
        foreach (int i in list)
        {
            if (oldList.Keys.Contains(i))
            {
                newList.Add(i, i);
            }
        }

        oldList = new Dictionary<int, int>(newList);
        newList.Clear();
    }

    return oldList.Values.ToList();
}

To proste rozwiązanie, jeśli wszystkie listy są małe. Jeśli masz większe listy, nie działa tak wydajnie, jak zestaw skrótów:

public static IEnumerable<T> IntersectMany<T>(this IEnumerable<IEnumerable<T>> input)
{
    if (!input.Any())
        return new List<T>();

    return input.Aggregate(Enumerable.Intersect);
}