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

Voici ma tentative pour résoudre le problème. Cela est basé sur cette stratégie mais emprunte également des idées de la réponse acceptée.

public static class EnumerableExtensions
{
    public static bool SequenceEqualUnordered(this IEnumerable source, IEnumerable second)
    {
        return SequenceEqualUnordered(source, second, EqualityComparer.Default);
    }

    public static bool SequenceEqualUnordered(this IEnumerable source, IEnumerable second, IEqualityComparer comparer)
    {
        if (source == null)
            throw new ArgumentNullException(nameof(source));

        if (second == null)
            throw new ArgumentNullException(nameof(second));

        if (source.TryGetCount(out int firstCount) && second.TryGetCount(out int secondCount))
        {
            if (firstCount != secondCount)
                return false;

            if (firstCount == 0)
                return true;
        }

        IEqualityComparer> wrapperComparer = comparer != null ? new WrappedItemComparer(comparer) : null;

        Dictionary, int> counters;
        ValueTuple key;
        int counter;

        using (IEnumerator enumerator = source.GetEnumerator())
        {
            if (!enumerator.MoveNext())
                return !second.Any();

            counters = new Dictionary, int>(wrapperComparer);

            do
            {
                key = new ValueTuple(enumerator.Current);

                if (counters.TryGetValue(key, out counter))
                    counters[key] = counter + 1;
                else
                    counters.Add(key, 1);
            }
            while (enumerator.MoveNext());
        }

        foreach (TSource item in second)
        {
            key = new ValueTuple(item);

            if (counters.TryGetValue(key, out counter))
            {
                if (counter <= 0)
                    return false;

                counters[key] = counter - 1;
            }
            else
                return false;
        }

        return counters.Values.All(cnt => cnt == 0);
    }

    private static bool TryGetCount(this IEnumerable source, out int count)
    {
        switch (source)
        {
            case ICollection collection:
                count = collection.Count;
                return true;
            case IReadOnlyCollection readOnlyCollection:
                count = readOnlyCollection.Count;
                return true;
            case ICollection nonGenericCollection:
                count = nonGenericCollection.Count;
                return true;
            default:
                count = default;
                return false;
        }
    }

    private sealed class WrappedItemComparer : IEqualityComparer>
    {
        private readonly IEqualityComparer _comparer;

        public WrappedItemComparer(IEqualityComparer comparer)
        {
            _comparer = comparer;
        }

        public bool Equals(ValueTuple x, ValueTuple y) => _comparer.Equals(x.Item1, y.Item1);

        public int GetHashCode(ValueTuple obj) => _comparer.GetHashCode(obj.Item1);
    }
}

Améliorations apportées à la solution de Microsoft :

• Ne prend pas le raccourci ReferenceEquals(first, second) car c'est un peu discutable. Par exemple, considérez un IEnumerable personnalisé qui a une implémentation comme ceci : public IEnumerator GetEnumerator() => Enumerable.Repeat(default(T), new Random().Next(10)).GetEnumerator().
• Prend des raccourcis possibles lorsque les deux énumérables sont une collection mais vérifie non seulement pour ICollection mais aussi pour d'autres interfaces de collection.
• Gère correctement les valeurs nulles. Compter les valeurs nulles séparément des autres valeurs (non nulles) ne semble pas non plus totalement fiable. Considérez un comparateur d'égalité personnalisé qui gère les valeurs nulles d'une manière non standard.

Cette solution est également disponible dans mon package NuGet utilitaire.