Merge intersecting items in a list of lists

user_7161242 0
Viewed 435

I have list of lists where i would like to merge all lists which contain identical values and make a new list out of the merged lists using linq. Here's and example:

var animalGroups = new List<List<Animal>>{    
    new List<Animal>{lizard,cat,cow,dog},
    new List<Animal>{horse, chicken, pig, turkey},
    new List<Animal>{ferret,duck,cat,parrot},
    new List<Animal>{chicken,sheep,horse,rabbit}
   };

The desired output would be a new List<List<animal>> containing the following List<Animal>:

{lizard, cat, cow, dog, ferret, duck, parrot} 
{horse,  chicken, pig, turkey, sheep, rabbit}

I'm rather new to linq and i got stuck at grouping the intersected lists without creating duplicates.

merge list linq .net c#
3 Answers

Here is the possible output with list of strings

    var animalGroups = new List<List<string>>
    {
        new List<string> {"lizard", "cat", "cow", "dog"},
        new List<string> {"horse", "chicken", "pig", "turkey"},
        new List<string> {"ferret", "duck", "cat", "parrot"},
        new List<string> {"chicken", "sheep", "horse", "rabbit"}
    };

    List<List<string>> mergedList = new List<List<string>>();
    for (int i = 0; i < animalGroups.Count; i++)
    {
        for (int j = i+1; j < animalGroups.Count; j++)
        {
            if (animalGroups[i].Intersect(animalGroups[j]).Any())
            {
                mergedList.Add(animalGroups[i].Concat(animalGroups[j]).Distinct().ToList());
            }
        }
    }
user_37680280

First, remember to override Equals and GetHahCode and/or implement IEquatable<Animal> in your Anymial class meaningfully(f.e. by comparing the Name).

List<IEnumerable<Animal>> mergedLists = animalGroups.MergeIntersectingLists().ToList();

Following extension method used which works with any type:

public static IEnumerable<IEnumerable<T>> MergeIntersectingLists<T>(this IEnumerable<IEnumerable<T>> itemLists, IEqualityComparer<T> comparer = null) 
{
    if (comparer == null) comparer = EqualityComparer<T>.Default;

    var itemListDict = new Dictionary<T, HashSet<T>>(comparer);
    foreach (IEnumerable<T> sequence in itemLists)
    {
        IList<T> list = sequence as IList<T> ?? sequence.ToList();
        HashSet<T> itemStorage = null;
        list.FirstOrDefault(i => itemListDict.TryGetValue(i, out itemStorage));
        // FirstOrDefault will initialize the itemStorage because its an out-parameter
        bool partOfListIsContainedInOther = itemStorage != null;

        if (partOfListIsContainedInOther)
        {
            // add this list to the other storage (a HashSet that removes duplicates)
            foreach (T item in list)
                itemStorage.Add(item);
        }
        else
        {
            itemStorage = new HashSet<T>(list, comparer);
            // each items needs to be added to the dictionary, all have the same storage
            foreach (T item in itemStorage)
                itemListDict.Add(item, itemStorage); // same storage for all
        }
    }

    // Distinct removes duplicate HashSets because of reference equality
    //  needed because item was the key and it's storage the value
    //  and those HashSets are the same reference
    return itemListDict.Values.Distinct();  
}
user_2842400

Your question is vague one; in case you want to combine 0, 2, 4, ... 2n as well as 1, 3, 5, ... 2n - 1 lists and you are looking for Linq solution:

  // I don't have Animal class, that's why I've put string
  // Be sure that Animal implements Equals as well as GetHashCode methods
  var animalGroups = new List<List<string>> {
    new List<string> {"lizard", "cat", "cow", "dog"},
    new List<string> {"horse", "chicken", "pig", "turkey"},
    new List<string> {"ferret", "duck", "cat", "parrot"},
    new List<string> {"chicken", "sheep", "horse", "rabbit"}
  };

  var result = animalGroups
    .Select((list, index) => new {
      list = list,
      index = index, })
     .GroupBy(item => item.index % 2, // grouping 0, 2, ... 2n as well as 1, 3,... 2n - 1 
              item => item.list)
     .Select(chunk => chunk
        .SelectMany(c => c)
        .Distinct()
        .ToList())
     .ToList();

Let's visualize the result:

  string test = string.Join(Environment.NewLine, result
    .Select(list => string.Join(", ", list)));

  Console.WritelLine(test);

Outcome

lizard, cat, cow, dog, ferret, duck, parrot
horse, chicken, pig, turkey, sheep, rabbit
user_23194070
Related