Vérifiez si une collection de valeurs contient un autre

Question

Supposons que j'ai deux collections comme suit:

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

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

toutes les valeurs sont des valeurs de chaîne. Je veux savoir si tous les éléments de Collection1 sont contenus dans Collection2, mais je n'ai aucune garantie sur la commande et un ensemble peut avoir plusieurs entrées avec la même valeur. Dans ce cas, Collection2 contient Collection1 parce que Collection2 a deux A1, M1 et M2. Theres la façon évidente: triant les deux collections et les valeurs de saut à mesure que je trouve des correspondances, mais je me demandais s'il existe une manière plus rapide et plus efficace de le faire. Encore une fois avec les collections initiales je ne garantie sur l'ordre ou combien de fois une valeur donnée apparaîtrai

EDIT: Modification ensemble à la collecte juste pour éclaircir que ceux-ci ne sont pas ensembles, car ils peuvent contenir des valeurs en double

Answer 1

Oui, il y a un moyen plus rapide, à condition que vous n'ayez pas d'espace limité. (Voir space/time tradeoff.)

L'algorithme:

Il suffit d'insérer tous les éléments Set2 dans un Hashtable (en C# 3.5, qui est un HashSet<string>), puis passer par tous les éléments de Set1 et vérifier si elles re dans la hashtable. Cette méthode est plus rapide (time (m + n) complexité temporelle), mais utilise l'espace O (n).

Sinon, dites:

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

---

Edit 1:

Pour les personnes concernées par la possibilité de doublons (et donc le terme impropre "ensemble"), l'idée peut facilement être étendu:

Juste faire un nouveau Dictionary<string, int> représentant le nombre de chaque mot dans la super-liste (ajouter un au compte chaque fois que vous voyez une instance d'un mot existant, et ajoutez le mot avec un nombre de 1 si ce n'est pas dans le dictionnaire), puis parcourez la sous-liste et décrémentez le compte à chaque fois. Si chaque mot existe dans le dictionnaire et le compte n'est jamais nul lorsque vous essayez de le décrémenter, alors le sous-ensemble est en fait une sous-liste; Sinon, vous avez trop d'instances d'un mot (ou il n'existe pas du tout), donc ce n'est pas une vraie sous-liste.

---

Edit 2:

Si les chaînes sont très grandes et vous êtes préoccupés par l'efficacité de l'espace, et un algorithme qui fonctionne avec (très) forte probabilité fonctionne pour vous, essayez de stocker une hacher de chaque chaîne à la place. Il n'est techniquement pas garanti de fonctionner, mais la probabilité qu'il ne fonctionne pas est très faible.

Answer 2

Découvrez 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

Le problème que je vois avec le HashSet, Intersection, et d'autres réponses Set théorie est que vous ne contiennent des doublons, et « Un ensemble est une collection qui ne contient aucun élément en double ». Voici un moyen de gérer les cas en double.

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

EDIT: Je renommé Set1 et Set2 à list1 et list2 pour apaiser Mehrdad.

EDIT 2: Le commentaire l'implique, mais je voulais indiquer explicitement que cela modifie la liste2. Faites-le de cette façon seulement si vous l'utilisez comme comparaison ou contrôle mais que vous n'avez pas besoin du contenu par la suite.

Answer 4

similaires un

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 façon la plus concise que je connaisse:

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