The opposite of Intersect()

Question

Intersect can be used to find matches between two collections, like so:

// Assign two arrays.
int[] array1 = { 1, 2, 3 };
int[] array2 = { 2, 3, 4 };
// Call Intersect extension method.
var intersect = array1.Intersect(array2);
// Write intersection to screen.
foreach (int value in intersect)
{
    Console.WriteLine(value); // Output: 2, 3
}

However what I'd like to achieve is the opposite, I'd like to list items from one collection that are missing from the other:

// Assign two arrays.
int[] array1 = { 1, 2, 3 };
int[] array2 = { 2, 3, 4 };
// Call "NonIntersect" extension method.
var intersect = array1.NonIntersect(array2); // I've made up the NonIntersect method
// Write intersection to screen.
foreach (int value in intersect)
{
    Console.WriteLine(value); // Output: 4
}

As a side note, this type of set is called a [Symmetric Difference](http://en.wikipedia.org/wiki/Symmetric_difference). — Mike T, Aug 14 '12 at 21:17
Technically speaking, a Symmetric Difference would result into [1, 4]. Since Peter wanted just the elements in array2 that are not in array1 (i.e., 4), that's called a [Relative Complement](http://en.wikipedia.org/wiki/Complement_(set_theory)) (aka Set-Theoretic Difference) — rtorres, Jul 17 '14 at 15:31

score 446 · Accepted Answer · answered Apr 11 '11 at 10:56

446

As stated, if you want to get 4 as the result, you can do like this:

var nonintersect = array2.Except(array1);

If you want the real non-intersection (also both 1 and 4), then this should do the trick:

var nonintersect = array1.Except(array2).Union( array2.Except(array1));

This will not be the most performant solution, but for small lists it should work just fine.

answered Apr 11 '11 at 10:56

Øyvind Bråthen

59,338
27
124
151

7

You can probably do it faster by using two nested for loops, but the code will be way dirtier than this. Counting readability into this also, I would clearly use this variant as it's very easy to read. – Øyvind Bråthen Jan 04 '12 at 15:10
6

Just a sideline point to add, If you have: int[] before = { 1, 2, 3 }; int[] after = { 2, 3, 3, 4 }; and you try to use Except to find what's been added to 'after' since 'before': var diff = after.Except(before); 'diff' contains 4, not 3,4. i.e. watch out for duplicate elements giving you unexpected results – Dwighte Aug 09 '13 at 00:09
Would this perform better? array1.AddRange(array2.Except(array1)); – LBW Jun 15 '18 at 12:58

score 96 · Answer 2 · answered Apr 11 '11 at 10:57

96

You can use

a.Except(b).Union(b.Except(a));

Or you can use

var difference = new HashSet(a);
difference.SymmetricExceptWith(b);

answered Apr 11 '11 at 10:57

sehe

374,641
47
450
633

2

Interesting use of SymmetricExceptWith(), I wouldn't have thought of that approach – Peter Bridger Apr 11 '11 at 11:09
1

`SymmetricExceptWith` is probably my favourite method. – Ash Clarke Apr 22 '13 at 15:00
6

I compared the two in a real application where I had a couple lists of about 125 strings in each of them. Using the first approach is actually faster for lists of that size, though its mostly insignificant as both approaches where under half a millisecond. – Dan May 31 '13 at 13:16
1

Would be nice if the BCL had a Linq extension method for this. It seems like an omission. – Drew Noakes Jun 30 '15 at 12:13
Someone benchmarked SymmetricExceptWith and found it much faster: http://www.skylark-software.com/2011/07/linq-and-set-notation.html – Colin Jul 18 '17 at 18:20

CodesInChaos · Answer 3 · 2014-04-08T11:29:12.553

13

This code enumerates each sequence only once and uses Select(x => x) to hide the result to get a clean Linq-style extension method. Since it uses HashSet<T> its runtime is O(n + m) if the hashes are well distributed. Duplicate elements in either list are omitted.

public static IEnumerable<T> SymmetricExcept<T>(this IEnumerable<T> seq1,
    IEnumerable<T> seq2)
{
    HashSet<T> hashSet = new HashSet<T>(seq1);
    hashSet.SymmetricExceptWith(seq2);
    return hashSet.Select(x => x);
}

edited Apr 08 '14 at 11:29

answered Apr 11 '11 at 11:00

CodesInChaos

106,488
23
218
262

I like the extension method, but I'm not sure about the .Select(x => x). Don't you think it add some unnecessary overhead ? – Filimindji Jan 29 '22 at 13:31

score 6 · Answer 4 · edited Aug 04 '17 at 08:49

6

array1.NonIntersect(array2);

Nonintersect such operator is not present in Linq you should do

except -> union -> except

a.except(b).union(b.Except(a));

edited Aug 04 '17 at 08:49

pix

1,264
19
32

answered Nov 15 '14 at 12:05

safder

95
1
1

score 6 · Answer 5 · answered Apr 11 '11 at 10:57

I think you might be looking for Except:

The Except operator produces the set difference between two sequences. It will only return elements in the first sequence that don't appear in the second. You can optionally provide your own equality comparison function.

Check out this link, this link, or Google, for more information.

score 2 · Answer 6 · edited Feb 12 '13 at 13:12

/// <summary>
/// Given two list, compare and extract differences
/// http://stackoverflow.com/questions/5620266/the-opposite-of-intersect
/// </summary>
public class CompareList
{
    /// <summary>
    /// Returns list of items that are in initial but not in final list.
    /// </summary>
    /// <param name="listA"></param>
    /// <param name="listB"></param>
    /// <returns></returns>
    public static IEnumerable<string> NonIntersect(
        List<string> initial, List<string> final)
    {
        //subtracts the content of initial from final
        //assumes that final.length < initial.length
        return initial.Except(final);
    }

    /// <summary>
    /// Returns the symmetric difference between the two list.
    /// http://en.wikipedia.org/wiki/Symmetric_difference
    /// </summary>
    /// <param name="initial"></param>
    /// <param name="final"></param>
    /// <returns></returns>
    public static IEnumerable<string> SymmetricDifference(
        List<string> initial, List<string> final)
    {
        IEnumerable<string> setA = NonIntersect(final, initial);
        IEnumerable<string> setB = NonIntersect(initial, final);
        // sum and return the two set.
        return setA.Concat(setB);
    }
}

score 2 · Answer 7 · answered Apr 11 '11 at 11:01

2

I'm not 100% sure what your NonIntersect method is supposed to do (regarding set theory) - is it
B \ A (everything from B that does not occur in A)?
If yes, then you should be able to use the Except operation (B.Except(A)).

answered Apr 11 '11 at 11:01

Frank Schmitt

30,195
12
73
107

Intersection of sets == A∪B\A∩B – amuliar Jan 04 '19 at 06:54

score -1 · Answer 8 · answered Jun 09 '17 at 16:18

string left = "411329_SOFT_MAC_GREEN";
string right= "SOFT_MAC_GREEN";

string[] l = left.Split('_');
string[] r = right.Split('_');

string[] distinctLeft = l.Distinct().ToArray();
string[] distinctRight = r.Distinct().ToArray();

var commonWord = l.Except(r, StringComparer.OrdinalIgnoreCase)
string result = String.Join("_",commonWord);
result = "411329"

The opposite of Intersect()

8 Answers8

Linked

Related