Comparing List<String> with duplicate information using Linq

Question

To compare two List<String> and extract their differences, I use Linq's Except.

i.e.:

Say I want to compare the following two lists for equality using Linq:

List1 = "0,1,2,2,3"
List2 = "0,1,2,3"

List<string> differences1 = List1.Except(List2).ToList();
List<string> differences2 = List2.Except(List1).ToList();

differences1 and differences2 will have no items as 2 exists in both lists, but both lists are NOT equal. I want to be able to extract all differences between the lists, including duplicate information one has that the other does not.

What is the best method of extracting all differences between two List<string> objects?

Have you tried using Distinct() to remove duplicates and comparing resulting lists? — semao
– semao, Commented Dec 17, 2013 at 15:24
I'm confused after the edit. You say you want "0,1,2,2,3" and "0,1,2,3" to be equal and you want to know that they are different. Huh? — Becuzz
– Becuzz, Commented Dec 17, 2013 at 15:37
@Becuzz No. List1 and List2 SHOULD be equal, which is why I am comparing them for validation. If they are different (including one having duplicate items) then I want to know WHY they are different. I am sorry if that was unclear. Not sure it warranted a downvote, however... — TestK
– TestK, Commented Dec 17, 2013 at 15:41

Servy · Accepted Answer · 2013-12-17 15:41:28Z

5

So what you're looking for is an Except that works on bags, not on sets. So if one sequence has 2 copies of an item and you subtract a set with one copy, there should be one copy left, rather than reducing all sequences into distinct sets before performing the subtraction, as Except does.

This makes it slightly less elegant to handle, but it's still not terrible. Rather than having a HashSet to represent the items in the other set, you simply need to have a dictionary mapping the item to the number of copies. Then for each item, if it's in the dictionary, remove one from the count and don't yield it, and if it isn't in the dictionary then it should be yielded.

public static IEnumerable<T> BagDifference<T>(IEnumerable<T> first
    , IEnumerable<T> second)
{
    var dictionary = second.GroupBy(x => x)
        .ToDictionary(group => group.Key, group => group.Count());

    foreach (var item in first)
    {
        int count;
        if (dictionary.TryGetValue(item, out count))
        {
            if (count - 1 == 0)
                dictionary.Remove(item);
            else
                dictionary[item] = count - 1;
        }
        else
            yield return item;
    }
}

answered Dec 17, 2013 at 15:41

Servy

204k27 gold badges347 silver badges470 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Servy Over a year ago

@TestK Your question is still not very clear; you should edit it to clarify it.

Servy Over a year ago

@TestK It does not, although it's better than it was before. As I said a while ago, you really should have some example input/output.

Hogan · Accepted Answer · 2013-12-17 15:21:31Z

0

You could group by the key and then compare the groups using Except()

It would look like this (not tested might have typos):

var groupList1 = List1.GroupBy(x => x).ToList();
var groupList2 = List2.GroupBy(x => x).ToList();

var differences1 = groupList1.Except(groupList2).ToList();
var differences2 = groupList2.Except(groupList1).ToList();

answered Dec 17, 2013 at 15:21

Hogan

70.7k10 gold badges83 silver badges119 bronze badges

Comments

Zach · Accepted Answer · 2013-12-17 15:25:02Z

0

You could call .Distinct() on the lists before comparing them:

List<string> differences1 = List1.Distinct().Except(List2).ToList();
List<string> differences2 = List2.Distinct().Except(List1).ToList();

answered Dec 17, 2013 at 15:25

Zach

4473 gold badges10 silver badges28 bronze badges

1 Comment

Servy Over a year ago

There's no point in calling Distinct before using Except; Except itself will remove duplicates.

Becuzz · Accepted Answer · 2013-12-17 15:26:29Z

0

You could use Distinct to eliminate the duplicates then do the comparison.

var distinctList1 = List1.Distinct().ToList();
var distinctList2 = List2.Distinct().ToList();

var differences1 = distinctList1.Except(distinctList2).ToList();
var differences2 = distinctList2.Except(distinctList1).ToList();

answered Dec 17, 2013 at 15:26

Becuzz

6,86728 silver badges39 bronze badges

1 Comment

Servy Over a year ago

There's no point in calling Distinct before using Except; Except itself will remove duplicates.

erikH · Accepted Answer · 2013-12-17 15:58:37Z

0

You could create duplicates of the list and then remove all that exists in the other:

var diff1 = list1.ToList();
var diff2 = list2.ToList();
diff1.RemoveAll(diff2.Remove);

answered Dec 17, 2013 at 15:58

erikH

2,3461 gold badge17 silver badges19 bronze badges

2 Comments

Servy Over a year ago

1) This is mutating both collections, rather than simply determining what the difference is. 2) This will perform really horribly, as searching for and then removing items from lists is not cheap.

erikH Over a year ago

Bad performance indeed! But that must not always be an issue. Though a simple solution to get the difference.

Collectives™ on Stack Overflow

Comparing List<String> with duplicate information using Linq

5 Answers 5

2 Comments

Comments

1 Comment

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

2 Comments

Comments

1 Comment

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related