Compare two lists, where order doesn't matter, using IEqualityComparer

Question

I want to check if two lists contain the same items. The order of the items doesn't matter, and the same items might appear twice in each list.

For example:

var List1 = new List<int> { 1, 2, 2 };
var List2 = new List<int> { 2, 1, 2 };
//equal

var List1 = new List<int> { 1, 2, 2 };
var List2 = new List<int> { 2, 1, 1 };
//not equal - different quantities of 1s and 2s in the two lists

Currently I do this as follows:

var List2copy = List2.ToList();
if (List1.Count != List2.Count) return false;
return List1.All(x => List2copy.Remove(x));

Now however I need to use an IEqualityComparer for the two items, which Remove cannot accept. Can anyone think of an efficient solution for the problem? It would also be useful if it accepted an IEnumerable rather than a List

Can you order the lists first? Then you could do a normal [SequenceEqual](https://msdn.microsoft.com/en-us/library/bb348567(v=vs.110).aspx)? — RB., Apr 25 '18 at 08:08
Why you don't use the `.Contains()` method of the Collection (`List<>`)? — R. García, Apr 25 '18 at 08:09
https://stackoverflow.com/questions/12795882/quickest-way-to-compare-two-list Take a look at this — Asakuraa Ranger, Apr 25 '18 at 08:10
@AsakuraaRanger That wont work if there's more than one matching item — Yair Halberstadt, Apr 25 '18 at 08:11
I think this will suit your needs https://stackoverflow.com/questions/12795882/quickest-way-to-compare-two-list — Van VO, Apr 25 '18 at 08:11
Use `Intersect` which also takes `IEqualityComparer`. Another solution can be convert each list to dictionary where Key would be equivalent to the item and Value would be count of item appeared in list. Later you can compare both the Dictionaries. — user1672994, Apr 25 '18 at 08:11
@VanVO Nope. That only works if two items in the same list aren't equal — Yair Halberstadt, Apr 25 '18 at 08:11
@RB not easily. Theyre quite complex objects, containing sub lists, which would have to be sorted first to make sure that the order would be the same. i'd rather avoid that if possible. — Yair Halberstadt, Apr 25 '18 at 08:14
@RenéVogt The IEqualityComparer is doing a lot of work - it's actually comparing sublists in the the two objects in the same way already, so to sort them would require sorting all the sub-lists too. That might be expensive. I'm hoping that there may be a simpler way. — Yair Halberstadt, Apr 25 '18 at 08:17
What about this? https://stackoverflow.com/questions/630263/c-compare-contents-of-two-ienumerables — Matthew Layton, Apr 25 '18 at 08:18
@series0ne I think the fourth answer down might be applicable, albeit ugly. Checking it out. — Yair Halberstadt, Apr 25 '18 at 08:20
@YairHalberstadt I'm not sure comparing hash sets is the right way to go about it, because `{2, 2, 1}` and `{1, 1, 2}` would be considered equal. — Matthew Layton, Apr 25 '18 at 08:23
@series0ne It's the otherwise section of that answer that's applicable — Yair Halberstadt, Apr 25 '18 at 08:24
@YairHalberstadt - When asking a question it is nice to at least have code that compiles. — Enigmativity, Apr 25 '18 at 10:48

score 5 · Answer 1 · answered Apr 25 '18 at 08:20

5

Try this should work for your situation:

return ListA.OrderBy(x => x).SequenceEqual(ListB.OrderBy(x => x));

Just a temporary order then compare

answered Apr 25 '18 at 08:20

Asakuraa Ranger

577
7
18

Enigmativity · Answer 2 · 2018-04-25T13:51:22.330

0

Another option you could try is:

var lookup1 = List1.ToLookup(x => x);
var lookup2 = List2.ToLookup(x => x);

return lookup1.Count == lookup2.Count && lookup1.All(x => lookup2[x.Key].SequenceEqual(x));

This doesn't require a full sort and may return the results more quickly.

edited Apr 25 '18 at 13:51

answered Apr 25 '18 at 10:50

Enigmativity

113,464
11
89
172

What if `List2` has more keys than `List1`, you'd need to check both ways. – Lasse V. Karlsen Apr 25 '18 at 10:56
@LasseVågsætherKarlsen - Excellent point. It's an even better solution now with a simple `.Count` comparison at the beginning. No sense proceeding unless they are the same. – Enigmativity Apr 25 '18 at 13:52

score -1 · Answer 3 · answered Apr 25 '18 at 08:35

A solution that you could perhaps use is:

Create 2 lists with distinct values of the original lists.
Intersect the 2 distinct value lists into 1 list containing all distinct values.
For each item in the combined distinct value list, count the amount of occurrences in each original list

Code:

var list1 = new List<int>{1,2,2};
var list2 = new List<int>{1,1,2};
var list1Distinct = list1.Distinct();
var list2Distinct = list1.Distinct();
var allDistinctValues = list1.Intersect(list2);
bool listsEqual = true;

foreach(int i in allDistinctValues)
{
    int list1Count=0;
    int list2Count=0;
    list1Count = list1.Count(val => val == i);
    list2Count = list2.Count(val => val == i);
    if(list1Count != list2Count)
    {
        listsEqual = false;
    }
}

if(!listsEqual)
{
    //List item counts not the same
}

Compare two lists, where order doesn't matter, using IEqualityComparer

3 Answers3

Linked