合并列表中重叠的项目

Question

我有一个列表的列表，希望将所有包含相同值的列表合并，并使用linq从合并后的列表中创建一个新列表。以下是示例：

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

所需输出应为包含以下List<Animal>的新List<List<animal>>：

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

我对LINQ还比较陌生，我在将交集列表分组时遇到了困难，不想生成重复项。

- CareCat

---

那么...按照它们共享任何值的方式对输入列表进行分组，然后将每个组合并到它们自己的列表中？ - Rawling

你对分组有什么规则？所有偶数索引列表放在一个列表中，所有奇数索引列表放在另一个列表中吗？=！ - Mong Zhu

如果超过2个列表彼此相交怎么办？我不理解哪些列表属于一个新列表的规则。 - Tim Schmelter

@TimSchmelter 如果超过两个列表相交，则它们应该合并为一个列表。很抱歉我忘记提到了这一点，但在我实现代码的地方不应该有问题。回答您的第二个问题：我并不是真的在尝试防止什么。我正在从程序中选择对象，并且我希望在代码的后续处理中将相交的选择处理为单个选择。 - CareCat

@TimSchmelter 应该排除没有交集的动物列表。我没有考虑到这一点，因为在我实现代码的情况下不应该出现这种情况，但如果包括这样的列表，它将产生错误。 - CareCat

Answer 1

这是可能的输出和字符串列表。

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

- Abhay

---

@CareCat，你在评论中说：“如果超过两个列表相交，则它们都应合并为一个列表”，但这段代码并没有实现这一点。 - Rawling

如果我考虑“如果超过两个列表相交，则应将它们全部合并为一个列表”，则无法工作。 - Martina

Answer 2

首先，记得在你的Animal类中有意义地覆盖Equals和GetHashCode方法和/或实现IEquatable<Animal>(例如，通过比较名称)。

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

以下扩展方法可与任何类型一起使用：

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

- Tim Schmelter

---

这是否涵盖了一个第三个列表将之前分离的两个列表连接在一起的情况？ - Rawling

@Rawling：如果第三个列表包含了之前某个列表中已经存在的项目，则该列表中的所有项目都将进入该列表（重复项将被删除）。如果第二个列表包含了第一个列表的项目，则第二个列表将与第一个列表合并。因此，最终您将拥有一个单一的列表，因为所有三个列表至少共享一个项目。 - Tim Schmelter

如果你有"AB"和"CD"，那么你会得到[A] -> "AB"，[B] -> "AB"，[C] -> "CD"，[D] -> "CD"（集合共享而不是重复）。如果你添加了"BC"，难道你最终不会得到[A] -> "ABC"，[B] -> "ABC"，[C] -> "CD"，[D] -> "CD"吗？ - Rawling

@CareCat：扩展方法对字符串或任何其他类型（包括值类型）都适用。如果您采用Abhay的示例数据，则返回以下结果：List<IEnumerable<string>> mergedLists = animalGroups.MergeIntersectingLists().ToList(); - Tim Schmelter

@TimSchmelter 抱歉，我指的是由字符'A'和'B'组成的集合"AB"。我懒得一遍又一遍地打出"集合"这个词了。 - Rawling

Answer 3

你的问题比较模糊；如果你想要将0, 2, 4, ... 2n和1, 3, 5, ... 2n - 1这两个列表合并，并且正在寻找Linq解决方案：

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

让我们来可视化结果：

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

  Console.WritelLine(test);

结果

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

- Dmitry Bychenko