c# - 如何从一组整数组中找到最小的不同组？

Question

假设我有一个类如下...

public class IntGroup {
  public string GroupName {get; set;}
  public List<int> Integers {get; set;}
}

...我有几个实例，每个实例都包含一个整数集合。我想找到包含不同整数的最小组集。

例如，如果我有以下组...

第 1 组包含 1、2、3
第 2 组包含 4、5、6
第 3 组包含 4、5、9

...然后，由于第 1 组包含三个不属于任何其他组的整数，它本身就是一组最小的组(在本例中为一组)。第 2 组和第 3 组是另一个最小的集合，因为您需要两个组都在一起(因为它们都包含 4 和 5)，但它们不需要第 1 组。

我想编写一些 C# 代码来帮助我找到这些最小的组。这是我认为可以在 Linq 中非常优雅地解决的问题，但我不知道如何解决。

有人能帮忙吗？顺便说一下，这不是家庭作业问题，我是一名 51 岁的程序员，希望解决一个更大的问题的一部分，该问题与构建函数调用树有关，并希望找到树的不同部分。

感谢您提供的任何帮助。

Answer 1

先定义这个类:

class ValueIEnumerableComparer<T> : IEqualityComparer<IEnumerable<T>>
{
    public bool Equals(IEnumerable<T> x, IEnumerable<T> y)
    {
        return x.SequenceEqual(y);
    }

    public int GetHashCode(IEnumerable<T> obj)
    {
        return obj.Sum(i => i.GetHashCode());
    }
}

然后，你可以使用这个链:

int[][] groups =
{
    new[] {1, 2, 3}, 
    new[] {4, 5, 6},
    new[] {4, 5, 9}
};
var result = groups.
    GroupBy(array => groups.
        Where(other => array != other).
        SelectMany(other => array.Intersect(other)), 
            new ValueIEnumerableComparer<int>()).
    Select(g => g.ToArray()).
    ToArray();

它所做的是按交集对数组进行分组，然后仅从组中选择数组。定义一个类实现 IEqualityComparer<IEnumerable<T>>是必要的。如果不定义比较器来比较它们的元素，我找不到更好的方法来提取两个序列的键。它的GetHashCode()方法不是很花哨，但适用于此示例。

它也可以很容易地适应你的情况，但我认为带一个通用的对阅读这个问题的人更有帮助。