how to ensure a List<String> contains each string in a sequence exactly once

Question

Suppose I have a list of strings, like this:

var candidates = new List<String> { "Peter", "Chris", "Maggie", "Virginia" };

Now I'd like to verify that another List<String>, let's call it list1, contains each of those candidates exactly once. How can I do that, succintly? I think I can use Intersect(). I also want to get the missing candidates.

private bool ContainsAllCandidatesOnce(List<String> list1)
{
     ????
}


private IEnumerable<String> MissingCandidates(List<String> list1)
{
     ????
}

Order doesn't matter.

Answer 1

This may not be optimal in terms of speed, but both queries are short enough to fit on a single line, and are easy to understand:

private bool ContainsAllCandidatesOnce(List<String> list1)
{
    return candidates.All(c => list1.Count(v => v == c) == 1);
}

private IEnumerable<String> MissingCandidates(List<String> list1)
{
    return candidates.Where(c => list1.Count(v => v == c) != 1);
}

Answer 2

Here we are talking about Except, Intersect and Distinct. I could have used a lamba operator with expression but it would have to loop over each and every item. That functionality is available with a predefined functions.

for your first method

var candidates = new List<String> { "Peter", "Chris", "Maggie", "Virginia" };

private bool ContainsAllCandidatesOnce(List<String> list1)
{
    list1.Intersect(candidates).Distinct().Any();
}

This will give any element from list1 which are in common in candidates list or you can do it the other way

candidates.Intersect(list1).Distinct().Any();

for your second method

private IEnumerable<String> MissingCandidates(List<String> list1)
{
    list1.Except(candidates).AsEnumerable();
}

This will remove all elements from list1 which are in candidates. If you wants it the other way you can do

candidates.Except(list1).AsEnumerable();

Answer 3

This should be quite efficient:

IEnumerable<string> strings  = ...

var uniqueStrings = from str in strings
                    group str by str into g
                    where g.Count() == 1
                    select g.Key;

var missingCandidates = candidates.Except(uniqueStrings).ToList();
bool isValid = !missingCandidates.Any();

1. Filter out repeats.
2. Ensure that all the candidates occur in the filtered-out-set.

Answer 4

GroupJoin is the right tool for the job. From msdn:

GroupJoin produces hierarchical results, which means that elements from outer are paired with collections of matching elements from inner. GroupJoin enables you to base your results on a whole set of matches for each element of outer.

If there are no correlated elements in inner for a given element of outer, the sequence of matches for that element will be empty but will still appear in the results.

So, GroupJoin will find any matches from the target, for each item in the source. Items in the source are not filtered if no matches are found in the target. Instead they are matched to an empty group.

Dictionary<string, int> counts = candidates
 .GroupJoin(
   list1,
   c => c,
   s => s,
   (c, g) => new { Key = c, Count = g.Count()
 )
 .ToDictionary(x => x.Key, x => x.Count);

List<string> missing = counts.Keys
  .Where(key => counts[key] == 0)
  .ToList();

List<string> tooMany = counts.Keys
  .Where(key => 1 < counts[key])
  .ToList();