List, equals

Two C# Lists may be equal when element order is ignored. We develop an algorithm to test for this condition. Order, and element counts, matter here.

Some problem notes

There are many possible approaches, but we want the simplest. We look at some research and develop a C# solution.

An example

We use Dictionary and compare frequencies. We see a generic method—it receives parameters of a caller-specified type. The syntax uses the angle brackets.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var la = new List<int>() { 1, 0, 4, 200, -40 };
        var lb = new List<int>() { -40, 200, 4, 1, 0 };
        var lc = new List<int>() { 3, 5, 4, 9, 11 };
        var ld = new List<int>() { 6, 6, 100 };
        var le = new List<int>() { 6, 100, 100 };
        Console.WriteLine(UnorderedEqual(la, lb));
        Console.WriteLine(UnorderedEqual(la, lc));
        Console.WriteLine(UnorderedEqual(lc, ld));
        Console.WriteLine(UnorderedEqual(ld, le));

        var a1 = new int[] { 1, 2, 5 };
        var a2 = new int[] { 2, 5, 1 };
        var a3 = new int[] { 1, 1, 3 };
        var a4 = new int[] { 3, 3, 1 };
        Console.WriteLine(UnorderedEqual(a1, a2));
        Console.WriteLine(UnorderedEqual(a1, a3));
        Console.WriteLine(UnorderedEqual(a3, a4));
    }

    static bool UnorderedEqual<T>(ICollection<T> a, ICollection<T> b)
    {
        // Require that the counts are equal.
        if (a.Count != b.Count)
        {
            return false;
        }
        // Initialize new Dictionary of the type.
        var d = new Dictionary<T, int>();
        // Add each key's frequency from collection A to the Dictionary.
        foreach (T item in a)
        {
            int c;
            if (d.TryGetValue(item, out c))
            {
                d[item] = c + 1;
            }
            else
            {
                d.Add(item, 1);
            }
        }
        // Add each key's frequency from collection B to the Dictionary.
        // ... Return early if we detect a mismatch.
        foreach (T item in b)
        {
            int c;
            if (d.TryGetValue(item, out c))
            {
                if (c == 0)
                {
                    return false;
                }
                else
                {
                    d[item] = c - 1;
                }
            }
            else
            {
                // Not in dictionary
                return false;
            }
        }
        // Verify that all frequencies are zero.
        foreach (int v in d.Values)
        {
            if (v != 0)
            {
                return false;
            }
        }
        // We know the collections are equal.
        return true;
    }
}
True
False
False
False
True
False
False

Notes, dictionary

The Dictionary used in this method is for storing each key of type T and its frequency. If a specific key is found once, its frequency will be set to 1, for example.

List 1 contents: 1, 2, 4
List 2 contents: 2, 1, 4
Equal?:          True

List 1 contents: 5, 4, 6
List 2 contents: 6, 5, 4
Equal?:          True

List 1 contents: 1, 2, 4
List 2 contents: 1, 4
Equal?:          False

List 1 contents: 1, 5
List 2 contents: 2, 5
Equal?:          False

List 1 contents: 1, 2
List 2 contents: 1, 2
Equal?:          True

Generics

We use a custom generic. You can rewrite the solution simply by changing the arguments to int[], and the Dictionary and loops to use int instead of T.

A summary

We saw a solution to checking unordered elements that is a generic method, which works for both string and int. It uses Dictionary and avoids excessive lookups.