.NET如何检查两个IEnumerable<T>是否具有相同的元素

Question

可能重复:
比较两个集合的相等性

我需要验证两个 IEnumerable<T> 列表是否具有相同的元素，不一定按相同顺序。

我正在针对 .NET 3.5 进行开发。

以下是测试。问题是，应该如何实现 HasSameElements()？

var l1 = new[]{1,2,3};
var l2 = new[]{3,1,2};

bool rez1 = l1.HasSameElements(l2);//should be true

var l3 = new[]{1,2,3,2};
var l4 = new[]{3,1,2,2};
bool rez2 = l3.HasSameElements(l4);//should be true

var l5 = new[]{1,2,3,2};
var l6 = new[]{1,2,3};
bool rez3 = l5.HasSameElements(l6);//should be false

附加说明：

• 在示例中我使用了IEnumerable，但T可以是任何类型。T是否必须实现IComparable接口？

• Enumerable.SequenceEquals()本身不起作用，它期望元素的顺序相同。

• 这是HasElements的模板：

[只是一些占位符文本，解决Markdown“代码格式”错误的问题]

public static class Extensions {
    public static bool HasElements(this IEnumerable<T> l1, IEnumerable<T> l2){
        throw new NotImplementedException();
    } 
}

- Cristian Diaconescu

---

https://dev59.com/jHVD5IYBdhLWcg3wNY1Z - Mitch Wheat

@Mitch：把这个评论变成答案，我会接受它。 - Cristian Diaconescu

问题是重复的，但更好的答案在这里：https://dev59.com/73A65IYBdhLWcg3wsgyA - Budda

Answer 1

只需建立一个字典，将每个对象映射到其在序列中出现的次数，然后检查结果字典是否相等。

代码如下：

static class EnumerableExtensions {
    public static bool HasSameElementsAs<T>(
        this IEnumerable<T> first,
        IEnumerable<T> second
    ) {
        var firstMap = first
            .GroupBy(x => x)
            .ToDictionary(x => x.Key, x => x.Count());
        var secondMap = second
            .GroupBy(x => x)
            .ToDictionary(x => x.Key, x => x.Count());
        return 
            firstMap.Keys.All(x =>
                secondMap.Keys.Contains(x) && firstMap[x] == secondMap[x]
            ) &&
            secondMap.Keys.All(x =>
                firstMap.Keys.Contains(x) && secondMap[x] == firstMap[x]
            );
    }
}

显然，可以将重复的代码重构为辅助方法，但这只会混淆这里的想法。您可以变得更加高级，并接受IEqualityComparer用于GroupBy操作。此外，您应该通过添加null保护等措施来生产化代码。

- jason

---

有趣。GroupBy()的时间复杂度是O(n)吗？ - Cristian Diaconescu

@Cristi Diaconescu：是的，应该是O(n)。 - jason

Answer 2

虽然 Cristi 的基于 Except 的方法可能更好，但你也可以尝试以下方法：

source.Sort().SequenceEqual(target.Sort());

如果是针对单元测试，我不会担心性能问题。当然，您需要确保您的排序是稳定的。

- Richard Szalay

---

也就是说，如果包含的对象是可排序的... - Cristian Diaconescu

这在平均情况下是O(n log n)。我认为我的方法（https://dev59.com/6FHTa4cB1Zd3GeqPRnek#4044038）是`O(n)`。 - jason

Answer 3

由于输入可能包含重复项，因此不能使用Except。一种算法是：

if the lists contain a different number of elements return false

make a copy of listA
foreach element in listB 
  if the element exists in copyA remove the first match from copyA
  otherwise return false

如果要实现，您可以查看FluentAssert中.ShouldBeEqualTo()方法的逻辑。

- Handcraftsman

Answer 4

使用：

 return  l2.Count() == l1.Count() && l1.Intersect(l2).Count() == l2.Count();

你还可以传递一个自定义的比较器。

public static class Extensions
{
    public static bool HasElements(
        this IEnumerable<T> l1, 
        IEnumerable<T> l2,
        IEqualityComparer<T> comparaer)
    {
        l2.Count() == l1.Count() && 
        return l1.Intersect(l2, comparer).Count() == l2.Count();
    } 
}

- Aliostad

---

取决于哪个集合更大... - Mitch Wheat

无法工作。Enumerable.Intersect返回一个集合。new[]{2,2}.Intersect(new[]{2, 2})返回{2}。 - Cristian Diaconescu

这只是首先检查计数是否相等，非常简单。 - Aliostad

如果可以的话，你真的想避免两次遍历序列。 - jason

Answer 5

我会这样做：

 public static bool HasSameElements<T>(this IEnumerable<T> source, IEnumerable<T> target)
 {
     return (source.Count() == target.Count() && source.All(a => target.Contains(a)));
 }

- Suhumar

---

如果可以的话，你真的想避免两次遍历序列。 - jason