Set equality in linq

Question

I have two lists A and B (List). How to determine if they are equal in the cheapest way? I can write something like "(minus B) union (B minus A) = empty set" or combine them together and count the number of elements, but it's quite expensive. Is there a workaround?

Answer 1

Well, it depends on how you interpret your lists.

If you consider them tuples (so the order of the items in the lists matters), you can go with this code:

public bool AreEqual<T>(IList<T> A, IList<T> B) { if (A.Count != B.Count) return false; for (int i = 0; i < A.Count; i++) if (!A[i].Equals(B[i])) return false; } 

If you treat your lists as sets (so the order of the elements doesn't matter), then ... you are using the wrong data structures, I think:

  public bool AreEqual<T>(IList<T> A, IList<T> B) { HashSet<T> setA = new HashSet<T>(A); return setA.SetEquals(B); } 

Answer 2

If the ordering of the list items is relevant:

 bool areEqual = a.SequenceEqual(b); 

If lists should be treated as unordered sets:

 // assumes that the list items are ints bool areEqual = new HashSet<int>(a).SetEquals(b); 

(The constructor has SequenceEqual and HashSet<T> overloads that accept the IEqualityComparer<T> parameter if you need these functions.)

Answer 3

It depends on what you mean by "list of equal." If you mean that they contain the same objects, the solution Daniel proposed is fine, just select Union () two lists and count them.

If “equal” you mean that they have the same elements in the same order , it would be better for you to compare the number of both lists, then if they have the same count, just iterate with a simple for loop to compare each element from both lists with the same index. Less beautiful, but you can hardly be faster.

Answer 4

There is no shortcut here, unless the lists are sorted, in which case you can compare items one by one. And, obviously, I assume that the order does not matter, otherwise it is obvious that you can also compare them in turn.

Otherwise, I would suggest that the most efficient algorithm that you could get for large lists of elements would probably be something like this, using a hash table to track what you saw (warning: not verified, but should be clear what i get.)

 public static bool IsEqual<T>(this List<T> x1, List<T> x2) { if(x1.Count != x2.Count) return false; var x1Elements = new Dictionary<T, int>(); foreach(var item in x1) { int n; x1Elements.TryGetValue(item, out n); x1Elements[item] = n+1; } foreach(var item in x2) { int n; x1Elements.TryGetValue(item, out n); if(n <= 0) return false; // this element was in x2 but not x1 else x1Elements[item] = n-1; } // make sure x1 didn't have any elements // that weren't in x2 return x1Elements.Values.All(x => x == 0); } 

Answer 5

The first snapshot - if they contain the same elements, the union of both lists should have the same number of elements as any of the two lists.

 listA.Union(listB).Count() == listA.Count() 

Note. Unable to delete one list.

But this is probably still operation O(n²) .

Another solution - lists should have the same length and list. The list minus B should not contain any elements.

 (listA.Count() == listB.Count()) && !listA.Except(listB).Any()