When comparing two ListT> objects for equality, order [duplicate] is ignored.

Problem

Another question about comparing lists.

List<MyType> list1;
List<MyType> list2;

Regardless of where they are in the list, I need to double-check that they each have the same elements. On a list, any MyType object might appear several times. Is this something that can be checked using a built-in function? What if I promised that each element would only appear once in a list?

EDIT: Thanks for the responses, but I forgot to include that the number of occurrences of each element on both lists should be the same.

Asked by Bruno Teixeira

Solution #1

If you want them to be really equal (i.e. the same items and the same number of each item), I think that the simplest solution is to sort before comparing:

Enumerable.SequenceEqual(list1.OrderBy(t => t), list2.OrderBy(t => t))

Here is a solution that performs a bit better (about ten times faster), and only requires IEquatable, not IComparable:

public static bool ScrambledEquals<T>(IEnumerable<T> list1, IEnumerable<T> list2) {
  var cnt = new Dictionary<T, int>();
  foreach (T s in list1) {
    if (cnt.ContainsKey(s)) {
      cnt[s]++;
    } else {
      cnt.Add(s, 1);
    }
  }
  foreach (T s in list2) {
    if (cnt.ContainsKey(s)) {
      cnt[s]--;
    } else {
      return false;
    }
  }
  return cnt.Values.All(c => c == 0);
}

You can construct a version that takes a comparer for the dictionary to handle any data type as a key (for example, nullable types, as Frank Tzanabetis pointed out):

public static bool ScrambledEquals<T>(IEnumerable<T> list1, IEnumerable<T> list2, IEqualityComparer<T> comparer) {
  var cnt = new Dictionary<T, int>(comparer);
  ...

Answered by Guffa

Solution #2

I would tackle it this way if you don’t bothered about the amount of instances. You’ll get better results with hash sets than with plain iteration.

var set1 = new HashSet<MyType>(list1);
var set2 = new HashSet<MyType>(list2);
return set1.SetEquals(set2);

This will necessitate the use of override. On MyType, I implemented GetHashCode() and IEquatableMyType>.

Answered by recursive

Solution #3

This question is ambiguous in its current form. The following is the statement:

does not specify whether you want the two lists to have the same collection of objects or a different set of things.

If you want to make sure that all of the members in two collections are the same, regardless of order, you can use:

// lists should have same count of items, and set difference must be empty
var areEquivalent = (list1.Count == list2.Count) && !list1.Except(list2).Any();

If you want to make sure that two collections have the same set of members (and that duplicates in either are ignored), you can use the following formula:

// check that [(A-B) Union (B-A)] is empty
var areEquivalent = !list1.Except(list2).Union( list2.Except(list1) ).Any();

Using the set operations (Intersect, Union, Except) is more efficient than using methods like Contains. In my opinion, it also better expresses the expectations of your query.

EDIT: Now that you’ve explained your query, I can tell you that the first form is the one to use, because duplicates are a problem. Here’s a basic example to show that you can get the desired result:

var a = new[] {1, 2, 3, 4, 4, 3, 1, 1, 2};
var b = new[] { 4, 3, 2, 3, 1, 1, 1, 4, 2 };

// result below should be true, since the two sets are equivalent...
var areEquivalent = (a.Count() == b.Count()) && !a.Except(b).Any(); 

Answered by LBushkin

Solution #4

You might use this alternative in addition to Guffa’s solution to have a more shorthanded notation.

public static bool ScrambledEquals<T>(this IEnumerable<T> list1, IEnumerable<T> list2)
{
  var deletedItems = list1.Except(list2).Any();
  var newItems = list2.Except(list1).Any();
  return !newItems && !deletedItems;          
}

Answered by Thomas Luijken

Solution #5

This is what I’m thinking will work for you:

list1.All(item => list2.Contains(item)) &&
list2.All(item => list1.Contains(item));

If you want to make it stand out, replace it to:

list1.All(item => list2.Contains(item)) &&
list1.Distinct().Count() == list1.Count &&
list1.Count == list2.Count

Answered by Brian Genisio

Post is based on https://stackoverflow.com/questions/3669970/compare-two-listt-objects-for-equality-ignoring-order