Determine whether two lists contain the same sequences of objects in different orders in C#


The SequenceEqual method determines whether two IEnumerable sequences contain the same objects in the same order. There is a simple way to determine whether the lists contain the same objects in different orders: sort the objects and then call SequenceEqual. Unfortunately this solution requires that you sort the items somehow, and that may not always be possible.

If the objects implement IComparable, then you can compare them so you can sort them. The following code shows an extension method that determines whether two IComparable lists contain the same objects, possibly in different orders.

public static bool ComparableSequenceEqual
(this IEnumerable list1, IEnumerable list2)
where T : IComparable
{
// Order the items in each list.
var ordered1 =
from T item in list1
orderby item
select item;
var ordered2 =
from T item in list2
orderby item
select item;
// Compare the lists.
return ordered1.SequenceEqual(ordered2);
}

This code uses a LINQ query to sort the items in the two lists. It then calls SequenceEqual for the sorted lists.

As the preceding post mentions, if the class implements IComparable, then SequenceEqual tests object equality not reference equality.

If the objects in the lists do not implement IComparable, then you cannot use LINQ to sort them. If they provide a good hashing function, however, you can sort them by their hash codes. The following code shows how you can do that.

public static bool HashableSequenceEqual
(this IEnumerable list1, IEnumerable list2)
{
// Order the items in each list.
var ordered1 =
from T item in list1
orderby item.GetHashCode()
select item;
var ordered2 =
from T item in list2
orderby item.GetHashCode()
select item;
// Compare the lists.
return ordered1.SequenceEqual(ordered2);
}

This code uses LINQ to sort the items by their hash codes. It then calls SequenceEqual to see if the sequences are the same.

For this method to work, the objects must provide a good hash code. By default, objects seem to return a hashing of their references so two variables that refer to the same instance return the same hash code. This basically gives you reference equality.

It is important that you pick a good hash code. An obvious approach here would be to hash the first and last names and then combine them with ^. Unfortunately that would give the Person “Rod Stephens” the same hash code as “Stephens Rod.”

To avoid this case, this example uses the following hash code.

public override int GetHashCode()
{
int hash1 = FirstName.GetHashCode().GetHashCode();
int hash2 = LastName.GetHashCode();
return hash1 ^ hash2;
}

This code hashes the first name and then hashes the resulting hash code. It hashes the last name and combines the two codes. By treating the first and last names differently, the code avoids the problem where a reversed name gives the same hash code.

   

This entry was posted in LINQ, lists, miscellany, OOP. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *