Vérifier si une collection de valeurs en contient une autre

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 contenues dans Collection2, mais je n'ai aucune garantie sur le bon de commande et un jeu peut avoir plusieurs entrées avec la même valeur. Dans ce cas, Collection2 ne contiennent Collection1 parce que Collection2 a deux A1, M1 et M2. Theres le moyen le plus évident: le tri à la fois les collections et sautaient des valeurs que je trouve les matchs, mais je me demandais si il n'y est plus rapide, plus efficace pour ce faire. De nouveau avec l'initiale de collections, je n'ai aucune garantie sur le bon de commande ou combien de fois une valeur donnée apparaîtra

EDIT: modification de l'ensemble de la collection juste pour dissiper que ce ne sont pas des ensembles, car ils peuvent contenir des doublons

source d'informationauteur Megatron

  1. 18

    Oui, il y a un moyen plus rapide, si vous n'êtes pas les espaces restreints. (Voir l'espace/temps compromis.)

    L'algorithme:

    Il suffit d'insérer tous les éléments de Set2 dans une table de hachage (en C# 3.5, c'est un HashSet<string>), puis passez à travers tous les éléments de Set1 et vérifier si elles sont dans la table de hachage. Cette méthode est plus rapide (Θ(m + n) temps de complexité), mais utilise O(n) de l'espace.

    Sinon, il suffit de dire:

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

    Edit 1:

    Pour les personnes concernées au sujet de la possibilité de doublons (et d'où le terme impropre "set"), l'idée peut être facilement étendue:

    Simplement une nouvelle Dictionary<string, int> représentant le comte de chaque mot dans le super-liste (add-on pour le compte chaque fois que vous voyez une instance d'un mot existant et ajouter le mot avec un nombre de 1 si ce n'est pas dans le dictionnaire), et puis passer par la sous-liste et décrémenter le décompte à chaque fois. Si chaque mot existe dans le dictionnaire et le comte n'est jamais à zéro lorsque vous essayez de décrémentation, alors le sous-ensemble est en fait une sous-liste; sinon, vous avez eu trop d'occurrences d'un mot (ou il n'existe pas du tout), donc c'est pas un vrai sous-liste.

    Edit 2:

    Si les chaînes sont très grandes et vous êtes inquiet au sujet de l'efficacité de l'espace, et un algorithme qui fonctionne avec de (très) haute probabilité qui fonctionne pour vous, alors essayez de stocker une de hachage de chaque chaîne à la place. Techniquement c'est pas garanti de travail, mais la probabilité que cela ne fonctionne pas est vachement faible.

  2. 30

    La plus concise que je connaisse:

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

    Le problème que je vois avec le HashSet, se Croisent, et d'autres de la théorie des ensembles de réponses, c'est que vous ne contiennent des doublons, et "Un ensemble est une collection qui ne contient pas les éléments en double". Voici une façon de gérer le double de cas.

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

    MODIFIER: j'ai renommé de Set1 et Set2 à list1 et list2, pour les apaiser, Mehrdad.

    EDIT 2: Le commentaire laisse entendre, mais je tenais à le préciser explicitement que ce n'modifier la liste 2. Seulement le faire de cette façon, si vous l'utilisez comme une comparaison ou de contrôle, mais n'ont pas besoin du contenu par la suite.

  4. 3

    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);
}
  5. 0

    Similaire

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