how to ensure a List 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.

see this question: http://stackoverflow.com/questions/568347/how-do-i-use-linq-to-obtain-a-unique-list-of-properties-from-a-list-of-objects — David.Chu.ca, May 09 '12 at 00:05
for these kinds or question please provide question along with answer so that what you are asking and what you get becomes clear like what would these two methods return if list1 was `new List{"foo", "bar"}` and i want `new List{"bar", "foo"}`. — Nikhil Agrawal, May 09 '12 at 01:05

score 5 · Accepted Answer · answered May 09 '12 at 00:11

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);
}

Nikhil Agrawal · Answer 2 · 2012-05-09T01:15:09.507

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();

Ani · Answer 3 · 2012-05-09T00:18:31.050

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();

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

score 1 · Answer 4 · edited Jun 20 '20 at 09:12

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();

dkackman · Answer 5 · 2012-05-09T00:18:11.563

0

    private bool ContainsAllCandidatesOnce(List<String> list1)
    {
        return list1.Where(s => candidates.Contains(s)).Count() == candidates.Count();
    }

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

edited May 09 '12 at 00:18

answered May 09 '12 at 00:09

dkackman

15,179
13
69
123

score 0 · Answer 6 · answered May 09 '12 at 01:51

0

How about using a HashSet instead of List?

answered May 09 '12 at 01:51

skywqr

36
6

This would be more efficient on larger lists. – MrWuf May 09 '12 at 03:08

score -1 · Answer 7 · answered May 10 '12 at 03:08

private static bool ContainsAllCandidatesOnce(List<string> lotsOfCandidates)
{
    foreach (string candidate in allCandidates)
    {
        if (lotsOfCandidates.Count(t => t.Equals(candidate)) != 1)
        {
            return false;
        }
    }

    return true;
}

private static IEnumerable<string> MissingCandidates(List<string> lotsOfCandidates)
{
    List<string> missingCandidates = new List<string>();

    foreach (string candidate in allCandidates)
    {
        if (lotsOfCandidates.Count(t => t.Equals(candidate)) != 1)
        {
            missingCandidates.Add(candidate);
        }
    }

    return missingCandidates;
}

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

7 Answers7