Comprobar si una colección de valores contiene otro

Question

Supongamos que tengo dos colecciones de la siguiente manera:

Collection1: "A1" "A1" "M1" "M2"

Collection2: "M2 " "M3" "M1" "A1" "A1" "A2"

todos los valores son valores de cadena. Quiero saber si todos los elementos en Collection1 están contenidos en Collection2, pero no tengo ninguna garantía sobre el pedido y un conjunto puede tener múltiples entradas con el mismo valor. En este caso, Collection2 contiene Collection1 porque Collection2 tiene dos A1, M1 y M2. De la manera más obvia: clasificando colecciones y eliminando valores a medida que encuentro coincidencias, pero me preguntaba si existe una manera más rápida y eficiente de hacerlo. De nuevo con las colecciones iniciales no tengo ninguna garantía sobre el orden o cuántas veces aparecerá un valor dado

EDIT: Se cambió conjunto de la colección simplemente para aclarar que estos no son conjuntos, ya que pueden contener valores duplicados

Answer 1

Sí, hay una manera más rápida, siempre que no tenga limitaciones de espacio. (Ver space/time tradeoff.)

El algoritmo:

basta con insertar todos los elementos de Set2 en una tabla hash (en C# 3.5, que es un HashSet<string>), y luego ir a través de todos los elementos de Set1 y comprobar si están re en la tabla hash. Este método es más rápido (Θ (m + n) complejidad de tiempo), pero usa O (n) espacio.

Como alternativa, simplemente decir:

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

---

Edición 1:

Para aquellas personas preocupadas por la posibilidad de duplicados (y de ahí el término equivocado "set"), la idea puede se puede extender fácilmente:

Simplemente haga una nueva Dictionary<string, int> que represente el recuento de cada palabra en la super-lista (agregue una al recuento cada vez que vea una instancia de una palabra existente, y agregue la palabra con un recuento de 1 si no está en el diccionario), y luego vaya a la sublista y disminuya el recuento cada vez. Si cada palabra existe en el diccionario y el recuento nunca es cero cuando intenta disminuirlo, entonces el subconjunto es de hecho una sublista; de lo contrario, tenía demasiadas instancias de una palabra (o no existía en absoluto), por lo que no es una sublista real.

---

Edición 2:

Si las cadenas son muy grandes y que están preocupados por la eficiencia del espacio, y un algoritmo que trabaja con (muy) alta probabilidad de que funciona para usted, a continuación, intente almacenar una hash de cada cadena en su lugar. Técnicamente no está garantizado para funcionar, pero la probabilidad de que no funcione es bastante bajo.

Answer 2

Echa un vistazo 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); 
} 

Answer 3

El problema que veo con el HashSet, Intersección, y otras respuestas teoría de conjuntos es que no contienen duplicados, y "Un conjunto es una colección que no contiene elementos duplicados". Esta es una forma de manejar los casos duplicados.

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's a duplicate in list1 
bool areAllPresent = list1.All(i => list2.Remove(i)); 

EDITAR: Me cambió el nombre de Set 1 y Set 2 a LIST1 y lista2 para apaciguar Mehrdad.

EDIT 2: El comentario lo implica, pero quería indicar explícitamente que esto altera la lista2. Solo hágalo de esta manera si lo usa como una comparación o control, pero no necesita los contenidos después.

Answer 4

similares uno

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

Answer 5

La forma más concisa que conozco:

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