Проверьте, содержит ли один набор значений другой

Предположим, что у меня есть две коллекции:

Collection1: "A1" "A1" "M1" "М2"

Collection2: "M2" "M3" "M1" "A1" "A1" "А2"

все значения являются строковыми значениями. Я хочу знать, содержатся ли все элементы Collection1 в Collection2, но у меня нет гарантии на порядок, и набор может иметь несколько записей с одинаковым значением. В этом случае Collection2 содержит Collection1, потому что Collection2 имеет два A1, M1 и M2. Theres очевидным образом: сортировка обеих коллекций и выскакивание значений, когда я нахожу совпадения, но мне было интересно, есть ли более эффективный способ сделать это. Снова с исходными коллекциями у меня нет гарантии по порядку или сколько раз будет отображаться данное значение

EDIT: Изменен набор для коллекции, чтобы очистить, что они не являются наборами, поскольку они могут содержать повторяющиеся значения

Ответы

Ответ 1

Да, есть более быстрый способ, если вы не ограничены по пространству. (См. коммюнике пространства/времени.)

Алгоритм:

Просто вставьте все элементы в Set2 в хеш-таблицу (в С# 3.5, что HashSet <string> ), а затем пройдете все элементы Set1 и проверьте, находятся ли они в хеш-таблице. Этот метод выполняется быстрее (Θ (m + n)), но использует O (n) пространство.

В качестве альтернативы просто скажите:

bool isSuperset = new HashSet<string>(set2).IsSupersetOf(set1);

Изменить 1:

Для тех людей, которые обеспокоены возможностью дублирования (и, следовательно, неправильного "набора" ), идея может быть легко расширена:

Просто создайте новый Dictionary<string, int>, представляющий количество каждого слова в супер-списке (добавьте его в счетчик каждый раз, когда вы увидите экземпляр существующего слова, и добавьте слово со счетом 1, если оно не в словаре), а затем перейдите в список и уменьшите счетчик каждый раз. Если каждое слово существует в словаре, и счетчик никогда не равен нулю, когда вы пытаетесь уменьшить его, то подмножество на самом деле является под-списком; в противном случае у вас было слишком много экземпляров слова (или его вообще не было), поэтому он не является реальным под-списком.

Изменить 2:

Если строки очень большие, и вы обеспокоены эффективностью пространства, и для вас работает алгоритм, который работает с (очень) высокой вероятностью, а затем попытайтесь сохранить хэш каждой строки. Технически он не гарантированно работает, но вероятность того, что он не работает, довольно низок.

Ответ 2

Самый сжатый способ, которым я знаю:

//determine if Set2 contains all of the elements in Set1
bool containsAll = Set1.All(s => Set2.Contains(s));

Ответ 3

Проблема, которую я вижу с ответами HashSet, Intersect и другими Set, заключается в том, что вы имеете дубликаты, а "Набор - это коллекция, которая не содержит повторяющихся элементов". Здесь можно обрабатывать повторяющиеся случаи.

var list1 = new List<string> { "A1", "A1", "M1", "M2" };
var list2 = new List<string> { "M2", "M3", "M1", "A1", "A1", "A2" };

// Remove returns true if it was able to remove it, and it won't be there to be matched again if there a duplicate in list1
bool areAllPresent = list1.All(i => list2.Remove(i));

EDIT: я переименовал из Set1 и Set2 в list1 и list2, чтобы успокоить Mehrdad.

РЕДАКТИРОВАТЬ 2: комментарий подразумевает это, но я хотел явно указать, что это изменяет list2. Делайте это так, только если вы используете его в качестве сравнения или контроля, но впоследствии не нуждаетесь в содержимом.

Ответ 4

Отъезд linq...

string[] set1 = {"A1", "A1", "M1", "M2" };
string[]  set2 = { "M2", "M3", "M1", "A1", "A1", "A2" };

var matching = set1.Intersect(set2);

foreach (string x in matching)
{
    Console.WriteLine(x);
}

Ответ 5

Аналогичный

string[] set1 = new string[] { "a1","a2","a3","a4","a5","aa","ab" };
string[] set2 = new string[] {"m1","m2","a4","a6","a1" };

var a = set1.Select(set => set2.Contains(set));