HomeSearch

C# List Equals (If Elements Are the Same)

Implement an Equals method on the List type. See if elements in 2 lists are the same.
List, equals. Two Lists may be equal when element order is ignored. We develop an algorithm to test for this condition. Order, and element counts, matter here.List
Some problem notes. There are many possible approaches. 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, < and >.Dictionary

TryGetValue: TryGetValue is used instead of ContainsKey. The TryGetValue method eliminates extra hash key computations.

TryGetValueContainsKey

Also: UnorderedEqual receives ICollections and checks length. If the 2 parameters have different counts, they cannot be equal.

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; } } Output 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.

Key: The method places each element into the Dictionary as a key. If an element occurs twice, its frequency is incremented.

Further: 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.

Notes, verify keys. Finally, each key should have a frequency of 0. This ensures there are no extra elements in the first collection.
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
Generics. We use a custom generic. 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 Class, Method

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

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.
© 2007-2019 Sam Allen. Every person is special and unique. Send bug reports to info@dotnetperls.com.
Home
Dot Net Perls