C# List Element Equality

List element equality. Two Lists may be equal when element order is ignored.

We develop an algorithm to test for this condition. There are many possible approaches. We want the simplest. We look at some research and develop a C# solution.

Input and output

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

Example. Before developing the solution, I researched on Google and found a variety of approaches. One solution copies both Lists to arrays, sorts them, and then loops over the elements. The best versions use Dictionary and compare frequencies.

Here: We see a generic method—it receives parameters of a caller-specified type. The syntax uses the angle brackets, < and >.

C# program that tests List equality

using System;
using System.Collections.Generic;

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

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

    static bool UnorderedEqual<T>(ICollection<T> a, ICollection<T> b)
    {
	// 1
	// Require that the counts are equal
	if (a.Count != b.Count)
	{
	    return false;
	}
	// 2
	// Initialize new Dictionary of the type
	Dictionary<T, int> d = new Dictionary<T, int>();
	// 3
	// 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);
	    }
	}
	// 4
	// 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;
	    }
	}
	// 5
	// Verify that all frequencies are zero
	foreach (int v in d.Values)
	{
	    if (v != 0)
	    {
		return false;
	    }
	}
	// 6
	// We know the collections are equal
	return true;
    }
}

In this example, TryGetValue is used instead of ContainsKey. The TryGetValue method eliminates extra hash key computations. This enhances performance and yields a method that is faster than most.

TryGetValueContainsKey

UnorderedEqual receives ICollections and checks length. Two collections that implement ICollection<T> are received and their Counts are compared. If the two parameters don't have the same number of elements, they cannot be equal.

Note: The Dictionary used in this method is for storing each key of type T and its frequency.

And: If a specific key is found once, its frequency will be set to 1, for example.

The method places each element into the Dictionary as a key. If an element occurs twice, its frequency is incremented. TryGetValue helps avoid hash computations. Each element in the second collection is decremented in the Dictionary.

And: If any value goes below zero, we already know the collections are not equal.

Final steps. It verifies the keys. The method enforces that each key have a frequency of 0. This ensures there are no extra elements in the first collection. Here we know that the collections are equal.

Generics. I don't normally use custom generics. They add needless complexity to small programs. You can rewrite the above solution simply by changing the arguments to int[], and the Dictionary and loops to use int instead of T.

Generic MethodGeneric Class

However: The implementation here will work on both strings and numeric types, with no code changes.

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

Also: The solution iterates over each value in the Dictionary. This avoids many lookups.

Related Links