List Equals ExampleImplement an Equals method on the List type. See if elements in 2 lists are the same.
C#
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.
List
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.
Dictionary
Detail TryGetValue is used instead of ContainsKey. The TryGetValue method eliminates extra hash key computations.
TryGetValue
ContainsKey
Also UnorderedEqual receives ICollections and checks length. If the 2 parameters have different counts, they cannot be equal.
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.
Detail 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.
Detail Each key should have a frequency of 0. This ensures there are no extra elements in the first collection.
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.
Generic
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.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.