在比较这些项目的顺序的两个集合相等不管 [英] Comparing two collections for equality irrespective of the order of items in them

问题描述

我想比较两个集合（在C＃），但我不能确定有效地实现这一目标的最佳途径。

I would like to compare two collections (in C#), but I'm not sure of the best way to implement this efficiently.

我读过有关的其他线程<一href="http://stackoverflow.com/questions/43500/is-there-a-built-in-method-to-compare-collections-in-c"相对=nofollow> Enumerable.SequenceEqual ，但它不正是我要找的。什么

I've read the other thread about Enumerable.SequenceEqual, but it's not exactly what I'm looking for.

在我的情况下，两个集合是相等的，如果他们都包含相同的项目（不论顺序）。

In my case, two collections would be equal if they both contain the same items (no matter the order).

例如：

collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};

collection1 == collection2; // true

我最常做的是遍历一个集合中的每一项，看它是否存在于其他集合，然后依次通过其他集合的每个项目，看看它是否存在于第一个集合。 （我开始通过比较长度）。

What I usually do is to loop through each item of one collection and see if it exists in the other collection, then loop through each item of the other collection and see if it exists in the first collection. (I start by comparing the lengths).

if (collection1.Count != collection2.Count)
    return false; // the collections are not equal

foreach (Item item in collection1)
{
    if (!collection2.Contains(item))
        return false; // the collections are not equal
}

foreach (Item item in collection2)
{
    if (!collection1.Contains(item))
        return false; // the collections are not equal
}

return true; // the collections are equal

不过，这并不完全正确的，它可能不是最有效的办法比较两个集合是否相等。

However, this is not entirely correct, and it's probably not the most efficient way to do compare two collections for equality.

一个例子，我能想到的将是错误的：

An example I can think of that would be wrong is:

collection1 = {1, 2, 3, 3, 4}
collection2 = {1, 2, 2, 3, 4}

这将是等于我的实现。我应该算的时候每一个项目被发现的数量，并确保数量是相等的两个集合？

Which would be equal with my implementation. Should I just count the number of times each item is found and make sure the counts are equal in both collections?

---

的例子是某种形式的C＃（姑且称之为伪C＃），但是给你的答案在任何一种语言，你愿意的话，也没关系。

The examples are in some sort of C# (let's call it pseudo-C#), but give your answer in whatever language you wish, it does not matter.

注意：我用整数进行简单的例子，但我希望能够使用引用类型的对象了（他们不正确的键的行为，因为只有对象的引用相比，不是内容）。

Note: I used integers in the examples for simplicity, but I want to be able to use reference-type objects too (they do not behave correctly as keys because only the reference of the object is compared, not the content).

推荐答案

原来，微软已经有了这包括在其测试框架：的CollectionAssert.AreEquivalent

It turns out Microsoft already has this covered in its testing framework: CollectionAssert.AreEquivalent

备注

两个集合是相等的，如果他们   有在相同的相同元件   量，但在任何顺序。要素   是相等的，如果他们的价值是相等的，   不如果它们指的是同一个对象。

Two collections are equivalent if they have the same elements in the same quantity, but in any order. Elements are equal if their values are equal, not if they refer to the same object.

使用反射，我修改背后AreEquivalent的code（）来创建一个相应的相等比较。它比现有的答案更完整的，因为它需要空值考虑在内，实现的IEqualityComparer并具有一定的效率和边缘情况的检查。此外，它的微软的：）

Using reflector, I modified the code behind AreEquivalent() to create a corresponding equality comparer. It is more complete than existing answers, since it takes nulls into account, implements IEqualityComparer and has some efficiency and edge case checks. plus, it's Microsoft :)

public class MultiSetComparer<T> : IEqualityComparer<IEnumerable<T>>
{
    public bool Equals(IEnumerable<T> first, IEnumerable<T> second)
    {
        if (first == null) 
            return second == null;

        if (second == null)
            return false;

        if (ReferenceEquals(first, second)) 
            return true;

        var firstCollection = first as ICollection<T>;
        var secondCollection = second as ICollection<T>;
        if (firstCollection != null && secondCollection != null)
        {
            if (firstCollection.Count != secondCollection.Count)
                return false;

            if (firstCollection.Count == 0) 
                return true;
        }

        return !HaveMismatchedElement(first, second);
    }

    private static bool HaveMismatchedElement(IEnumerable<T> first, IEnumerable<T> second)
    {
        int firstNullCount;
        int secondNullCount;

        var firstElementCounts = GetElementCounts(first, out firstNullCount);
        var secondElementCounts = GetElementCounts(second, out secondNullCount);

        if (firstNullCount != secondNullCount || firstElementCounts.Count != secondElementCounts.Count)
            return true;

        foreach (var kvp in firstElementCounts)
        {
            var firstElementCount = kvp.Value;
            int secondElementCount;
            secondElementCounts.TryGetValue(kvp.Key, out secondElementCount);

            if (firstElementCount != secondElementCount)
                return true;
        }

        return false;
    }

    private static Dictionary<T, int> GetElementCounts(IEnumerable<T> enumerable, out int nullCount)
    {
        var dictionary = new Dictionary<T, int>();
        nullCount = 0;

        foreach (T element in enumerable)
        {
            if (element == null)
            {
                nullCount++;
            }
            else
            {
                int num;
                dictionary.TryGetValue(element, out num);
                num++;
                dictionary[element] = num;
            }
        }

        return dictionary;
    }

    public int GetHashCode(IEnumerable<T> enumerable)
    {
        int hash = 17;

        foreach (T val in enumerable.OrderBy(x => x))
            hash = hash * 23 + ((val == null) ? 42 : val.GetHashCode());

        return hash;
    }
}

这篇关于在比较这些项目的顺序的两个集合相等不管的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！