4
\$\begingroup\$

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?

\$\endgroup\$
2
  • 3
    \$\begingroup\$ What about { 0, 0, 1, 1 } and { 0, 1, 1, 1 } ? (assuming it should return false, as your current code seem to already do) \$\endgroup\$ Jan 18, 2015 at 19:00
  • \$\begingroup\$ @SimonAndreForsberg Yes it should return false in the case you asked. \$\endgroup\$ Jan 18, 2015 at 19:05

2 Answers 2

1
\$\begingroup\$

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)\$.

\$\endgroup\$
0
\$\begingroup\$

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);
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.