Vérifiez si un tableau est un sous-ensemble d'un autre

145

Une idée sur la façon de vérifier si cette liste est un sous-ensemble d'une autre?

Plus précisément, j'ai

List<double> t1 = new List<double> { 1, 3, 5 };
List<double> t2 = new List<double> { 1, 5 };

Comment vérifier que t2 est un sous-ensemble de t1, en utilisant LINQ?

Graviton
la source
Si les listes sont triées (comme dans votre exemple), cela devrait être possible en temps O (n + m).
Colonel Panic

Réponses:

255
bool isSubset = !t2.Except(t1).Any();
Cameron MacFarland
la source
1
J'ai créé la méthode d'extension geekswithblogs.net/mnf/archive/2011/05/13/…
Michael Freidgeim
@Bul Ikana Le fonctionnement de ce code est simple, la méthode d'extension appelle en interne les méthodes Equals et GetHashCode des méthodes de classe d'objets surchargées s'il n'y a pas de IEqualityComparer fourni pour le travail.
Mrinal Kamboj
2
Si les listes sont de longueur n et m, quelle est la complexité temporelle de cet algorithme?
Colonel Panic
2
Ce serait bien si cela se résumait à une méthode linq appelée ContainsAll
Sebastian Patten
60

Utilisez HashSet au lieu de List si vous travaillez avec des ensembles. Ensuite, vous pouvez simplement utiliser IsSubsetOf ()

HashSet<double> t1 = new HashSet<double>{1,3,5};
HashSet<double> t2 = new HashSet<double>{1,5};

bool isSubset = t2.IsSubsetOf(t1);

Désolé qu'il n'utilise pas LINQ. :-(

Si vous avez besoin d'utiliser des listes, la solution de @ Jared fonctionne avec l'avertissement que vous devrez supprimer tous les éléments répétés qui existent.

Tvanfosson
la source
3
Exactement. Vous voulez une opération d'ensemble, utilisez la classe conçue pour eux. La solution de Cameron est créative, mais pas aussi claire / expressive que le HashSet.
technophile
2
Euh, je ne suis pas d'accord car la question dit spécifiquement "utiliser LINQ".
JaredPar
9
@JaredPar: Et alors? Ne vaut-il pas mieux montrer à quelqu'un la bonne voie que la voie qu'il souhaite suivre?
Jonathan Allen
Une liste conserve son ordre mais pas un ensemble. Si l'ordre est important, cela donnerait des résultats incorrects.
UuDdLrLrSs
11

Si vous effectuez des tests unitaires, vous pouvez également utiliser la méthode CollectionAssert.IsSubsetOf :

CollectionAssert.IsSubsetOf(subset, superset);

Dans le cas ci-dessus, cela signifierait:

CollectionAssert.IsSubsetOf(t2, t1);
Géza
la source
7

C'est une solution nettement plus efficace que les autres publiées ici, en particulier la meilleure solution:

bool isSubset = t2.All(elem => t1.Contains(elem));

Si vous pouvez trouver un seul élément dans t2 qui n'est pas dans t1, alors vous savez que t2 n'est pas un sous-ensemble de t1. L'avantage de cette méthode est qu'elle se fait entièrement en place, sans allouer d'espace supplémentaire, contrairement aux solutions utilisant .Except ou .Intersect. De plus, cette solution est capable de s'interrompre dès qu'elle trouve un élément unique qui viole la condition du sous-ensemble, tandis que les autres continuent la recherche. Vous trouverez ci-dessous la forme longue optimale de la solution, qui n'est que légèrement plus rapide dans mes tests que la solution abrégée ci-dessus.

bool isSubset = true;
foreach (var element in t2) {
    if (!t1.Contains(element)) {
        isSubset = false;
        break;
    }
}

J'ai fait une analyse rudimentaire des performances de toutes les solutions, et les résultats sont drastiques. Ces deux solutions sont environ 100 fois plus rapides que les solutions .Except () et .Intersect () et n'utilisent aucune mémoire supplémentaire.

utilisateur2325458
la source
C'est exactement ce que nous !t2.Except(t1).Any()faisons. Linq travaille d'avant en arrière. Any()demande à un IEnumerables'il y a au moins un élément. Dans ce scénario t2.Except(t1)n'émet que le premier élément t2dont n'est pas t1. Si le premier élément de t2n'est pas t1dedans, il se termine le plus rapidement, si tous les éléments de y t2sont, t1il s'exécute le plus longtemps.
ABTO
Tout en jouant avec une sorte de référence, j'ai découvert, quand vous prenez t1={1,2,3,...9999}et t2={9999,9998,99997...9000}, vous obtenez les mesures suivantes: !t2.Except(t1).Any(): 1ms -> t2.All(e => t1.Contains(e)): 702ms. Et c'est pire avec la portée.
ABTO
2
Ce n'est pas ainsi que fonctionne Linq. t2.Except (t1)renvoie un IEnumerablepas un Collection. Il n'émet tous les éléments possibles que si vous le parcourez complètement, par exemple par ToArray ()ou ToList ()ou utilisez foreachsans pénétrer à l'intérieur. Recherchez l' exécution différée de linq pour en savoir plus sur ce concept.
ABTO
1
Je suis pleinement conscient du fonctionnement de l'exécution différée dans Linq. Vous pouvez différer l'exécution autant que vous le souhaitez, mais lorsque vous voulez déterminer si t2 est un sous-ensemble de t1, vous devrez parcourir toute la liste pour le comprendre. Il n'y a pas moyen de contourner ce fait.
user2325458
2
Prenons l'exemple de votre commentaire t2={1,2,3,4,5,6,7,8} t1={2,4,6,8} t2.Except(t1)=> premier élément de t2 = 1 => la différence de 1 à t1 est 1 (vérifiée par rapport à {2,4,6,8}) => Except()émet le premier élément 1 => Any()obtient un élément => Any()aboutit à vrai => aucune vérification supplémentaire des éléments de t2.
ABTO
6

@ La solution de Cameron comme méthode d'extension:

public static bool IsSubsetOf<T>(this IEnumerable<T> a, IEnumerable<T> b)
{
    return !a.Except(b).Any();
}

Usage:

bool isSubset = t2.IsSubsetOf(t1);

(Ceci est similaire, mais pas tout à fait le même que celui publié sur le blog de @ Michael)

Neil
la source
0

En me basant sur les réponses de @Cameron et @Neil, j'ai écrit une méthode d'extension qui utilise la même terminologie que la classe Enumerable.

/// <summary>
/// Determines whether a sequence contains the specified elements by using the default equality comparer.
/// </summary>
/// <typeparam name="TSource">The type of the elements of source.</typeparam>
/// <param name="source">A sequence in which to locate the values.</param>
/// <param name="values">The values to locate in the sequence.</param>
/// <returns>true if the source sequence contains elements that have the specified values; otherwise, false.</returns>
public static bool ContainsAll<TSource>(this IEnumerable<TSource> source, IEnumerable<TSource> values)
{
    return !values.Except(source).Any();
}
sclarke81
la source
0

Ici, nous vérifions que s'il y a un élément présent dans la liste enfant (c'est-à-dire t2) qui n'est pas contenu par la liste parent (c'est-à-dire t1) .Si aucun élément n'existe, alors la liste est un sous-ensemble de l'autre

par exemple:

bool isSubset = !(t2.Any(x => !t1.Contains(x)));
Lucifer
la source
-1

Essaye ça

static bool IsSubSet<A>(A[] set, A[] toCheck) {
  return set.Length == (toCheck.Intersect(set)).Count();
}

L'idée ici est que Intersect ne renverra que les valeurs qui se trouvent dans les deux tableaux. À ce stade, si la longueur de l'ensemble résultant est la même que celle de l'ensemble d'origine, alors tous les éléments de «set» sont également en «check» et donc «set» est un sous-ensemble de «toCheck»

Remarque: ma solution ne fonctionne pas si "set" a des doublons. Je ne le change pas parce que je ne veux pas voler les votes des autres.

Indice: j'ai voté pour la réponse de Cameron.

JaredPar
la source
4
Cela fonctionne s'il s'agit bien d'ensembles, mais pas si le deuxième «ensemble» contient des éléments répétés puisqu'il s'agit en réalité d'une liste. Vous pouvez utiliser HashSet <double> pour vous assurer qu'il a défini la sémantique.
tvanfosson
ne fonctionne pas lorsque les deux tableaux ont des éléments qui ne sont pas dans l'autre tableau.
da_berni