Check if array A contains all elements of array B and vice versa irrespective of order

Question

I am trying to check if an Array A contains all the elements of Array B and similarly Array B contains elements of Array A, the order does not matter.

Some examples:

A               B                Result 
{1}             {0}              false
{0, 0, 0}       {0, 0, 0}        true
{17, 4, 11}     {4, 17, 11}      true

I have written the following code:

public static bool CheckEquality(int[] a, int[] b) 
{
    return Array.TrueForAll(a, m => b.Count(z => m == z) == a.Count(z => m == z)) && a.Length == b.Length;
}

Both arrays contain just integers. Both arrays should strictly contain the same number of the same elements, and their lengths should be equal.

Is there a better and efficient way to do this?

Answer 1

You can check this by keeping track of each value in a dictionary: adding one for items in the first array, subtracting one for items in the second array and finally checking that all tracked values are zero.

Also, implemented this way, there is no need to make the method array- or int-specific.

public static bool CheckEquality<T>(IEnumerable<T> first, IEnumerable<T> second)
{
    var dictionary = new Dictionary<T, int>();

    Action<IEnumerable<T>, int> setCounts = (items, change) =>
    {
        foreach (var item in items)
        {
            int count;
            // if not found, count will be the default value of 0
            dictionary.TryGetValue(item, out count);
            dictionary[item] = count + change;
        }
    };

    setCounts(first, +1);
    setCounts(second, -1);

    return dictionary.Values.All(value => value == 0);
}

The code is more complicated than sorting arrays, but it's also \$O(n)\$.

Answer 2

Just another O(N) implementation:

UPDATE based on comments

public class EqualityTest
{
    [Test]
    [TestCase("1", "0", false)]
    [TestCase("0,0,0", "0,0,0", true)]
    [TestCase("17,4,11", "4,17,11", true)]
    [TestCase("0,0,1,1", "0,1,1,1", false)]
    public void CheckForEqualityTest(string aString, string bString, bool expected)
    {
        var a = aString.Split(',').Select(int.Parse);
        var b = bString.Split(',').Select(int.Parse);

        Assert.AreEqual(expected, CheckEquality(a,b));
    }

    private static bool CheckEquality<T>(IEnumerable<T> a, IEnumerable<T> b)
    {
        var aCounts = a.GroupBy(i => i).Select(g => Tuple.Create(g.Key, g.Count()));
        var bCounts = b.GroupBy(i => i).Select(g => Tuple.Create(g.Key, g.Count()));
        return new HashSet<Tuple<T, int>>(aCounts).SetEquals(bCounts);
    }
}

Answer 3

Using Linq is very easy; just use the Except() method:

var missingElementsInB = arrayA.Except(arrayB);

If missingElementsInB have any element both are not equal. So check vice versa:

var missingElementsInA = arrayB.Except(arrayA);

And this way you have the leftover elements in those arrays.