Comparer deux collections pour l'égalité, indépendamment de l'ordre des éléments qui s'y trouvent

Question

Je voudrais comparer deux collections (en C#), mais je ne suis pas sûr de la meilleure façon de le faire de manière efficace.

J'ai lu l'autre fil de discussion sur Enumerable.SequenceEqual, mais ce n'est pas exactement ce que je recherche.

Dans mon cas, deux collections seraient considérées comme égales si elles contiennent toutes deux les mêmes éléments (peu importe l'ordre).

Exemple:

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

collection1 == collection2; // true

Ce que je fais habituellement, c'est de parcourir chaque élément d'une collection et de vérifier s'il existe dans l'autre collection, puis de parcourir chaque élément de l'autre collection et de voir s'il existe dans la première collection. (Je commence par comparer les longueurs).

if (collection1.Count != collection2.Count)
    return false; // les collections ne sont pas égales

foreach (Item item in collection1)
{
    if (!collection2.Contains(item))
        return false; // les collections ne sont pas égales
}

foreach (Item item in collection2)
{
    if (!collection1.Contains(item))
        return false; // les collections ne sont pas égales
}

return true; // les collections sont égales

Cependant, ce n'est pas tout à fait correct, et ce n'est probablement pas la manière la plus efficace de comparer deux collections pour l'égalité.

Un exemple auquel je pense qui serait incorrect est:

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

Ce qui serait considéré comme égal avec ma mise en œuvre. Devrais-je simplement compter le nombre de fois où chaque élément est trouvé et m'assurer que les comptes sont égaux dans les deux collections?

---

Les exemples sont dans une sorte de C# (appelons cela pseudo-C#), mais donnez votre réponse dans la langue que vous souhaitez, cela n'a pas d'importance.

Remarque : J'ai utilisé des entiers dans les exemples pour simplifier, mais je veux pouvoir utiliser des objets de type référence aussi (ils ne se comportent pas correctement comme clés car seule la référence de l'objet est comparée, pas le contenu).

Answer 1

Une publication en double en quelque sorte, mais consultez ma solution pour comparer des collections. C'est assez simple :

Ceci effectuera une comparaison d'égalité indépendamment de l'ordre :

var list1 = new[] { "Bill", "Bob", "Sally" };
var list2 = new[] { "Bob", "Bill", "Sally" };
bool isequal = list1.Compare(list2).IsSame;

Ceci vérifiera si des éléments ont été ajoutés / supprimés :

var list1 = new[] { "Billy", "Bob" };
var list2 = new[] { "Bob", "Sally" };
var diff = list1.Compare(list2);
var onlyinlist1 = diff.Removed; //Billy
var onlyinlist2 = diff.Added;   //Sally
var inbothlists = diff.Equal;   //Bob

Ceci permettra de voir quels éléments du dictionnaire ont changé :

var original = new Dictionary() { { 1, "a" }, { 2, "b" };
var changed = new Dictionary() { { 1, "aaa" }, { 2, "b" } };
var diff = original.Compare(changed, (x, y) => x.Value == y.Value, (x, y) => x.Value == y.Value);
foreach (var item in diff.Different)
  Console.Write("{0} a changé en {1}", item.Key.Value, item.Value.Value);
//Résultera : a changé en aaa

Publication originale ici.

Answer 2

Cette solution simple force le type générique de IEnumerable à implémenter IComparable. En raison de la définition de OrderBy.

Si vous ne souhaitez pas faire une telle hypothèse mais que vous voulez quand même utiliser cette solution, vous pouvez utiliser le morceau de code suivant :

bool equal = collection1.OrderBy(i => i?.GetHashCode())
   .SequenceEqual(collection2.OrderBy(i => i?.GetHashCode()));

Answer 3

Voici ma variante de la méthode d'extension de la réponse d'ohadsc, au cas où elle serait utile à quelqu'un

public static class EnumerableExtensions 
{
    public static bool IsEquivalentTo(this IEnumerable first, IEnumerable second)
    {
        if ((first == null) != (second == null))
            return false;

        if (!object.ReferenceEquals(first, second) && (first != null))
        {
            if (first.Count() != second.Count())
                return false;

            if ((first.Count() != 0) && HaveMismatchedElement(first, second))
                return false;
        }

        return true;
    }

    private static bool HaveMismatchedElement(IEnumerable first, IEnumerable second)
    {
        int firstCount;
        int secondCount;

        var firstElementCounts = GetElementCounts(first, out firstCount);
        var secondElementCounts = GetElementCounts(second, out secondCount);

        if (firstCount != secondCount)
            return true;

        foreach (var kvp in firstElementCounts)
        {
            firstCount = kvp.Value;
            secondElementCounts.TryGetValue(kvp.Key, out secondCount);

            if (firstCount != secondCount)
                return true;
        }

        return false;
    }

    private static Dictionary GetElementCounts(IEnumerable enumerable, out int nullCount)
    {
        var dictionary = new Dictionary();
        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;
    }

    private static int GetHashCode(IEnumerable enumerable)
    {
        int hash = 17;

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

        return hash;
    }
}

Answer 4

Voici une solution qui est une amélioration par rapport à celle-ci.

public static bool HasSameElementsAs(
        this IEnumerable first, 
        IEnumerable second, 
        IEqualityComparer comparer = null)
    {
        var firstMap = first
            .GroupBy(x => x, comparer)
            .ToDictionary(x => x.Key, x => x.Count(), comparer);

        var secondMap = second
            .GroupBy(x => x, comparer)
            .ToDictionary(x => x.Key, x => x.Count(), comparer);

        if (firstMap.Keys.Count != secondMap.Keys.Count)
            return false;

        if (firstMap.Keys.Any(k1 => !secondMap.ContainsKey(k1)))
            return false;

        return firstMap.Keys.All(x => firstMap[x] == secondMap[x]);
    }

Answer 5

Basé sur cette réponse d'une question en double, et les commentaires ci-dessous la réponse, et @brian-genisio réponse j'ai trouvé ceci:

        public static bool AreEquivalentIgnoringDuplicates(this IEnumerable items, IEnumerable otherItems)
        {
            var itemList = items.ToList();
            var otherItemList = otherItems.ToList();
            var except = itemList.Except(otherItemList);
            return itemList.Count == otherItemList.Count && except.IsEmpty();
        }

        public static bool AreEquivalent(this IEnumerable items, IEnumerable otherItems)
        {
            var itemList = items.ToList();
            var otherItemList = otherItems.ToList();
            var except = itemList.Except(otherItemList);
            return itemList.Distinct().Count() == otherItemList.Count && except.IsEmpty();
        }

Tests pour ces deux:

        [Test]
        public void collection_with_duplicates_are_equivalent()
        {
            var a = new[] {1, 5, 5};
            var b = new[] {1, 1, 5};

            a.AreEquivalentIgnoringDuplicates(b).ShouldBe(true); 
        }

        [Test]
        public void collection_with_duplicates_are_not_equivalent()
        {
            var a = new[] {1, 5, 5};
            var b = new[] {1, 1, 5};

            a.AreEquivalent(b).ShouldBe(false); 
        }