Compare two List<T> objects for equality, ignoring order [duplicate]

Question

Yet another list-comparing question.

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

I need to check that they both have the same elements, regardless of their position within the list. Each MyType object may appear multiple times on a list. Is there a built-in function that checks this? What if I guarantee that each element appears only once in a list?

EDIT: Guys thanks for the answers but I forgot to add something, the number of occurrences of each element should be the same on both lists.

Meitner

You may be interested in this post, which shows how to fix the null handling issues of the dictionary-based solution while also improving performance. – Bouton

Answer 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))

Edit:

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);
}

Edit 2:

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

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

Humphries

This is a good answer, I believe it is correct, and it is shorter than mine. My only suggestion is to use SequenceEqual as an extension method. I should also point out that this requires that T be IComparable, whereas the ToLookup version only requires a correct GetHashCode and Equals implementation. – Hurty

I think this is the simplest approach. I'm using: list1.sort(); list2.sort(); return Enumerable.SequenceEquals(list1, list2); Now I'm having problems in comparing elements. Can you guys give me some pointers? In Java I only have to implement equals or hash, here it doesnt seem to work. Thanks – Meitner

This approach only works if MyType is comparable (or a custom comparer is supplied) and a total ordering of items is possible. Otherwise you can get false negatives. It's also doing more work than necessary - specifically, if the lists have a different number of items they can't possibly be equal. – Utgardloki

@Bruno Teixeira: Write a correct Equals and GetHashCode implementation; ideally implement IEquatable<T>. Then either implement IComparable<T> (ideally) and use this technique or use a ToLookup or some other associative-array technique. – Hurty

Hi, copypasted your code but last line gives me compilation error, Error 12 'System.Collections.Generic.Dictionary<T,int>.ValueCollection' does not contain a definition for 'All' and no extension method 'All' accepting a first argument of type 'System.Collections.Generic.Dictionary<T,int>.ValueCollection' could be found (are you missing a using directive or an assembly reference?) - any suggestions? – Vito

@AskarIbragimov: You need using System.Linq; at the top of the file. – Humphries

Thanks for the code, but only one problem with using a Dictionary - if T is a nullable type, a null in the passed in collection will cause it to fall over. Also, maybe rename the method to ScrambledEggs as that's how i read it the first time i saw it. Must be hungry... – Bahadur

@FrankTzanabetis: Good point. If you use a comparer for the dictionary, it can handle any data type as key. I added a note about that above. – Humphries

I have stumbled across your post and wanted to tell for future reference that the your method should check for nulls and counts to perform even better with larger list. Than two lists with either of one being null should return false and two lists with different counts should also return false its way faster than to iterate all elements of both lists if one list has 100.001 items and the other 100.000. :D – Gallicize

@Humphries OrderBy is so smartly but i checked the time consumption and it seems be the scrambledEquales is slower than first approach! Am I Wrong? Check Time code is : {Console.WriteLine(DateTime.Now.ToString("ss.ffffff")); Console.WriteLine(Enumerable.SequenceEqual(list1.OrderBy(s => s),list2.OrderBy(s => s))); Console.WriteLine(DateTime.Now.ToString("ss.ffffff")); Console.WriteLine(ScrambledEquals<string>(list1,list2)); Console.WriteLine(DateTime.Now.ToString("ss.ffffff"));} – Assumptive

@QMaster: The system clock has very low resolution (at least the last four digits in the output is completely arbitrary), and running the comparison only once gives too much interference from other factors. Use a Stopwatch for timing, and run the comparisons a lot of times to reduce the effect of other factrors. – Humphries

@Humphries Thanks, I had been Suspicious to system clock in most of scenario and you helped me about that too. but is your means for stopwatch the real one from hand watch or is an special class or extensions? – Assumptive

@QMaster: Naturally it's a class :) msdn.microsoft.com/en-us/library/… – Humphries

@Humphries stopwatch is a global name and mine is a big mistake :D Thanks again. – Assumptive

@Humphries Another small optimization could be to check if cnt[s]>0 when iterating the second list. If not, you can return false right away – Perdure

As a first step you should compare count of both lists (e.g. list1.Count() != list2.Count()). In case lists have different amount of items, you can return 'false' right away – Ludendorff

@Humphries Enumerable.SequenceEqual always return true for me. I'm comparing two list of objects with mixed string and integer values. – Trichome

I know this is old, but even if you add the IEqualityComparer paramater, if you try to iterate over a null list your going to get a null reference exception. You could add the following to the beginning of the function if (list1 == null && list2 == null) { return true; } if (list1 == null || list2 == null) { return false; } – Masturbation

I still can't for the life of me figure out how a comparer could be used to enable a dictionary to take null as key. – Fingerprint

@TwistedWhisper: If you provide a comparer when you create a dictionary, it will use that when it compares the keys. If the comparer handles a nullable type, you can use the null value as one of the keys in the dictionary. The dictionary doesn't care about the key values, it only cares what the comparer tells it about the key values. – Humphries

@Humphries Thanks for taking the time to comment. I'm actually looking at the source code of Dictionary<TKey, TValue>.Add(). The moment the key == null, it's throwing ArgumentNullException with or without comparer. github.com/microsoft/referencesource/blob/… I've even tried your codes with a comparer. No dice. I'm using .NET Core btw. – Fingerprint

Thanks for the simple one liner with LINQ. Have no idea why CollectionAssert.AreEqual() passes on Debug mode but fails on normal Run mode. Weird. – Sherasherar

Answer 2

If you don't care about the number of occurrences, I would approach it like this. Using hash sets will give you better performance than simple iteration.

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

This will require that you have overridden .GetHashCode() and implemented IEquatable<MyType> on MyType.

Centaury

Do I just need to implement the GetHashCode on MyType then? – Meitner

@recursive: This will not take into account duplicates, as the OP indicates he needs in his edit. This will, however, work if duplicates can be ignored. – Utgardloki

The HashSet<T> also needs you to implement the Equals method. The items are compared against each other, it's not just the hash codes that are compared. – Humphries

@Guffa: All the other approaches here require Equals also. – Centaury

@recursive: Yes, but the answer mentiones only GetHashCode, as if Equals would not be needed. – Humphries

You dont need set2 to be a hashset.. any enumerable would do – Maighdlin

Answer 3

As written, this question is ambigous. The statement:

... they both have the same elements, regardless of their position within the list. Each MyType object may appear multiple times on a list.

does not indicate whether you want to ensure that the two lists have the same set of objects or the same distinct set.

If you want to ensure to collections have exactly the same set of members 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 ensure two collections have the same distinct set of members (where duplicates in either are ignored), you can use:

// 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 clarified your question, I can say that you want to use the first form - since duplicates matter. Here's a simple example to demonstrate that you get the result you want:

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(); 

Utgardloki

The first method doesn't work in the following case: a = new[] {1,5,5} and b = new[] {1,1,5}. The collections don't have exactly the same set of members but areEquivalent is set to true. – Minutia

@Remko Jansen is right, the approach with !a.Except(b).Any() is BUGGY - it will say that a={2,2} and b={1,2} are equal. I wonder how it could take so much votes? – Ritornello

This answer doesn't take into account that the count can be the same and except can match but the list can still be different: { 1,1,2,2,3,3 } != { 1,2,3,4,5,6 } Even performing .Except(...) in the opposite direction doesn't solve the problem: { 1,1,2,3 } != { 1,2,2,3 } – Steepen

Here you can find my extension methods for collection comparison based on this answer, fixing issues mentioned in comments here: https://mcmap.net/q/102085/-comparing-two-collections-for-equality-irrespective-of-the-order-of-items-in-them – Antarctic

Answer 4

In addition to Guffa's answer, you could use this variant 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;          
}

Barnabas

This works, but if you want to make it run as optimal as possible, you might want to use return !(list1.Except(list2).Any()) && !(list2.Except(list1).Any()); (#EDIT: Damn, I can't make it work properly. Curse my newbiness.) – Prolongate

[1, 1, 2] and [2, 2, 1] would return true which is incorrect. – Fingerprint

Answer 5

Thinking this should do what you want:

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

if you want it to be distinct, you could change it to:

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

Antler

You can still get a false positive. Consider {1, 2, 2} and {1, 1, 2}, they contain the same items, has the same count, but still are not equal. – Humphries

@Guffa: Good point. I think I got it now, with the list1.Distinct() addition. If all the items are the same, and list 1 is distinct, and they both have the same lengths, then list 2 must also be distinct. Now, {1,2} and {2,1} are considered the same, but {1,2,2} and {1,1,2} are not. – Antler

While technically correct, the behavior of Contains() may result in O(N²) performance. The set operations (Except, Intersect, Union) perform much better if the number of items large. – Utgardloki

@Brian Genisio: Now get a false negative on {1, 2, 2} and {1, 2, 2}... – Humphries

@Guffa: You should. The lists are not distinct. The second answer assumes that the lists are distinct and contain the same values. – Antler

Answer 6

This is a slightly difficult problem, which I think reduces to: "Test if two lists are permutations of each other."

I believe the solutions provided by others only indicate whether the 2 lists contain the same unique elements. This is a necessary but insufficient test, for example {1, 1, 2, 3} is not a permutation of {3, 3, 1, 2} although their counts are equal and they contain the same distinct elements.

I believe this should work though, although it's not the most efficient:

static bool ArePermutations<T>(IList<T> list1, IList<T> list2)
{
   if(list1.Count != list2.Count)
         return false;

   var l1 = list1.ToLookup(t => t);
   var l2 = list2.ToLookup(t => t);

   return l1.Count == l2.Count 
       && l1.All(group => l2.Contains(group.Key) && l2[group.Key].Count() == group.Count()); 
}

Hurty

Answer 7

This worked for me:
If you are comparing two lists of objects depend upon single entity like ID, and you want a third list which matches that condition, then you can do the following:

var list3 = List1.Where(n => !List2.select(n1 => n1.Id).Contains(n.Id));

Refer: MSDN - C# Compare Two lists of objects

Nephograph

Answer 8

I use this method )

public delegate bool CompareValue<in T1, in T2>(T1 val1, T2 val2);

public static bool CompareTwoArrays<T1, T2>(this IEnumerable<T1> array1, IEnumerable<T2> array2, CompareValue<T1, T2> compareValue)
{
    return array1.Select(item1 => array2.Any(item2 => compareValue(item1, item2))).All(search => search)
            && array2.Select(item2 => array1.Any(item1 => compareValue(item1, item2))).All(search => search);
}

Cattycornered

Answer 9

try this!!!

using following code you could compare one or many fields to generate a result list as per your need. result list will contain only modified item(s).

// veriables been used
List<T> diffList = new List<T>();
List<T> gotResultList = new List<T>();



// compare First field within my MyList
gotResultList = MyList1.Where(a => !MyList2.Any(a1 => a1.MyListTField1 == a.MyListTField1)).ToList().Except(gotResultList.Where(a => !MyList2.Any(a1 => a1.MyListTField1 == a.MyListTField1))).ToList();
// Generate result list
diffList.AddRange(gotResultList);

// compare Second field within my MyList
gotResultList = MyList1.Where(a => !MyList2.Any(a1 => a1.MyListTField2 == a.MyListTField2)).ToList().Except(gotResultList.Where(a => !MyList2.Any(a1 => a1.MyListTField2 == a.MyListTField2))).ToList();
// Generate result list
diffList.AddRange(gotResultList);


MessageBox.Show(diffList.Count.ToString);

Strangles