LINQ : Determine if two sequences contains exactly the same elements

Question

I need to determine whether or not two sets contains exactly the same elements. The ordering does not matter.

For instance, these two arrays should be considered equal:

IEnumerable<int> data = new []{ 3,5,6,9 };
IEnumerable<int> otherData = new []{ 6,5,9,3}

One set cannot contain any elements, that are not in the other.

Can this be done using the built-in query operators ? And what would be the most efficient way to implement it, considering that the number of elements could range from a few to hundreds ?

Answer 1

Hi, This should help:

    IEnumerable<int> data = new []{ 3,5,6,9 };
    IEnumerable<int> otherData = new[] {6, 5, 9, 3};

    if(data.All(x => otherData.Contains(x)))
    {
        //Code Goes Here
    }

Answer 2

If you might have duplicates (or if you want a solution which performs better for longer lists), I'd try something like this:

static bool IsSame<T>(IEnumerable<T> set1, IEnumerable<T> set2)
{
    if (set1 == null && set2 == null)
        return true;
    if (set1 == null || set2 == null)
        return false;

    List<T> list1 = set1.ToList();
    List<T> list2 = set2.ToList();

    if (list1.Count != list2.Count)
        return false;

    list1.Sort();
    list2.Sort();

    return list1.SequenceEqual(list2);
}

UPDATE: oops, you guys are right-- the Except() solution below needs to look both ways before crossing the street. And it has lousy perf for longer lists. Ignore the suggestion below! :-)

Here's one easy way to do it. Note that this assumes the lists have no duplicates.

bool same = data.Except (otherData).Count() == 0;

Answer 3

1. First, check the length. If they are different, the sets are different.
2. you can do data.Intersect(otherData);, and check the length is identical.
3. OR, simplt sort the sets, and iterate through them.

Answer 4

I suggest sorting both, and doing an element-by-element comparison.

data.OrderBy(x => x).SequenceEqual(otherData.OrderBy(x => x))

I'm not sure how fast the implementation of OrderBy is, but if it's a O(n log n) sort like you'd expect the total algorithm is O(n log n) as well.

For some cases of data, you can improve on this by using a custom implementation of OrderBy that for example uses a counting sort, for O(n+k), with k the size of the range wherein the values lie.

Answer 5

If you want to treat the arrays as "sets" and ignore duplicate items, you can use HashSet<T>.SetEquals method:

var isEqual = new HashSet<int>(first).SetEquals(second);

Otherwise, your best bet is probably sorting both sequences in the same way and using SequenceEqual to compare them.