Distinct list of lists, where lists contains same values but in different order
I got a list:
var list = new List<List<int>>();
which could contain
list[0] = {1, 2, 3, 4}
list[1] = {3, 1, 2, 4}
list[2] = {2, 1, 7, 3}
How can I detect the duplicate between [0] and [1] and remove one of them? Code is c-sharp.
In reality it's not a int, but that shouldn't change the qu开发者_JAVA百科estion.
You could write your own implementation of IEqualityComparer<List<int>>
. For GetHashCode()
it would simply return the XOR of all the hash codes of the elements in the list. For Equals()
it would create a new HashSet<int>
from the first list, and call HashSet<T>.SetEquals
on it, passing in the second list. This assumes there will be no duplicate elements, mind you. (Otherwise { 1, 1, 2 } will be equal to { 1, 2, 2 } but have a different hash code.)
Once you've got that far, you can use Distinct
:
var distinct = list.Distinct(new CustomEqualityComparer());
As an alternative approach, could you use HashSet<T>
as your collection type to start with? Then it's really easy:
var distinct = sets.Distinct(HashSet<int>.CreateSetComparer());
If you need lists as the input but can cope with sets as the output:
var distinct = list.Select(x => new HashSet<int>(x))
.Distinct(HashSet<int>.CreateSetComparer());
Here's the euqality comparer Jon Skeet is talking about (his advice regarding working with HashSets to begin with is also spot on, of course):
public class EnumerableComparer<T> : IEqualityComparer<IEnumerable<T>>
where T : IComparable<T>
{
public bool Equals(IEnumerable<T> first, IEnumerable<T> second)
{
if (first == second)
return true;
if ((first == null) || (second == null))
return false;
return new HashSet<T>(first).SetEquals(second);
}
public int GetHashCode(IEnumerable<T> enumerable)
{
return enumerable.OrderBy(x => x)
.Aggregate(17, (current, val) => current*23 + val.GetHashCode());
}
}
So you'd do something like:
list.Distinct(new EnumerableComparer());
If the elements are not guaranteed to be unique - Use the IEqualityComparer
I posted here:
Comparing two collections for equality irrespective of the order of items in them
(In previous edits, I mistakingly posted an IEqulityComparer that compares between two lists of lists - could be very useful when dealing with partitions, but that's a different topic)
boolean compareLists(list1, list2) {
// Early rejection
if (list1.size != list2.size) {
return false;
}
// Sort lists and compare each item
sorted1 = sort(list1.clone());
sorted2 = sort(list2.clone());
for (int i=0; i<list1.size; ++i) {
if (sorted1[i]!=sorted2[i]) {
return false;
}
}
return true;
}
list[1] = list[1].Except(list[0]).ToList();
This is the solution in the assumption that we need to remove the duplicate ints from the arrays list[0]
and list[1]
. Other answers are dealing with the case of removing arrays which contain the same set of ints.
精彩评论