Compruebe si una matriz es un subconjunto de otra

145

¿Alguna idea sobre cómo verificar si esa lista es un subconjunto de otra?

Específicamente, tengo

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

¿Cómo verificar que t2 es un subconjunto de t1, usando LINQ?

Graviton
fuente
Si las listas están ordenadas (como en su ejemplo), esto debería ser posible en el tiempo O (n + m).
Coronel Panic

Respuestas:

255
bool isSubset = !t2.Except(t1).Any();
Cameron MacFarland
fuente
1
He creado el método de extensión geekswithblogs.net/mnf/archive/2011/05/13/…
Michael Freidgeim
@Bul Ikana El funcionamiento de este código es simple, el método de extensión llama internamente Equals y GetHashCode de los métodos de clase de objeto anulados si no se proporciona IEqualityComparer para el trabajo.
Mrinal Kamboj
2
Si las listas son de longitud ny m, ¿cuál es la complejidad temporal de este algoritmo?
Coronel Panic el
2
Sería bueno si esto se redujera a un método linq llamado ContainsAll
Sebastian Patten
60

Use HashSet en lugar de List si trabaja con conjuntos. Entonces puedes simplemente usar IsSubsetOf ()

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

bool isSubset = t2.IsSubsetOf(t1);

Lamento que no use LINQ. :-(

Si necesita usar listas, la solución de @ Jared funciona con la advertencia de que deberá eliminar cualquier elemento repetido que exista.

tvanfosson
fuente
3
Exactamente. Si desea una operación de configuración, use la clase diseñada para ellos. La solución de Cameron es creativa, pero no tan clara / expresiva como el HashSet.
tecnófilo
2
No estoy de acuerdo porque la pregunta específicamente dice "use LINQ".
JaredPar
9
@JaredPar: ¿Y qué? ¿No es mejor mostrarle a alguien el camino correcto que el que quiere?
Jonathan Allen
Una lista mantiene su orden pero un conjunto no. Si el pedido es importante, esto daría resultados incorrectos.
UuDdLrLrSs
11

Si realiza pruebas unitarias también puede utilizar el método CollectionAssert.IsSubsetOf :

CollectionAssert.IsSubsetOf(subset, superset);

En el caso anterior esto significaría:

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

Esta es una solución significativamente más eficiente que las otras publicadas aquí, especialmente la solución principal:

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

Si puede encontrar un solo elemento en t2 que no está en t1, entonces sabe que t2 no es un subconjunto de t1. La ventaja de este método es que se realiza todo en el lugar, sin asignar espacio adicional, a diferencia de las soluciones que usan .Except o .Intersect. Además, esta solución puede romperse tan pronto como encuentre un solo elemento que viole la condición del subconjunto, mientras que los demás continúan buscando. A continuación se muestra la forma larga óptima de la solución, que es solo marginalmente más rápida en mis pruebas que la solución abreviada anterior.

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

Hice un análisis de rendimiento rudimentario de todas las soluciones, y los resultados son drásticos. Estas dos soluciones son aproximadamente 100 veces más rápidas que las soluciones .Except () y .Intersect (), y no utilizan memoria adicional.

usuario2325458
fuente
Eso es exactamente lo que !t2.Except(t1).Any()está haciendo. Linq está trabajando de ida y vuelta. Any()está preguntando IEnumerablesi hay al menos un elemento. En este escenario t2.Except(t1)solo se emite el primer elemento del t2cual no está t1. Si el primer elemento de t2no está en t1él, termina más rápido, si todos los elementos de sí t2están en t1él, dura más.
abto
Mientras que jugar un poco con algún tipo de referencia, descubrí, cuando se toma t1={1,2,3,...9999}y t2={9999,9998,99997...9000}, se obtiene las siguientes medidas: !t2.Except(t1).Any(): 1ms -> t2.All(e => t1.Contains(e)): 702ms. Y empeora cuanto mayor es el rango.
abto
2
Así no es como funciona Linq. t2.Except (t1)está devolviendo un IEnumerableno a Collection. Solo emite todos los elementos posibles si itera completamente sobre él, por ejemplo, mediante ToArray ()o sin ToList ()usar foreachdentro. Busque la ejecución diferida de linq para leer más sobre ese concepto.
abto
1
Soy plenamente consciente de cómo funciona la ejecución diferida en Linq. Puede diferir la ejecución todo lo que desee, pero cuando desee determinar si t2 es un subconjunto de t1, deberá iterar toda la lista para resolverlo. No hay forma de evitar ese hecho.
user2325458
2
Tomemos el ejemplo de su comentario t2={1,2,3,4,5,6,7,8} t1={2,4,6,8} t2.Except(t1)=> primer elemento de t2 = 1 => la diferencia de 1 a t1 es 1 (verificado con {2,4,6,8}) => Except()emite el primer elemento 1 => Any()obtiene un elemento => Any()da como resultado verdadero => no más verificación de elementos en t2.
abto
6

La solución de @ Cameron como método de extensión:

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

Uso:

bool isSubset = t2.IsSubsetOf(t1);

(Esto es similar, pero no exactamente igual al publicado en el blog de @ Michael)

Neil
fuente
0

Sobre la base de las respuestas de @Cameron y @Neil, escribí un método de extensión que usa la misma terminología que la clase 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
fuente
0

Aquí verificamos que si hay algún elemento presente en la lista secundaria (es decir, t2que no está contenido en la lista principal (es decir t1)). Si no existe ninguno de ellos, entonces la lista está subconjunto

p.ej:

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

Prueba esto

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

La idea aquí es que Intersect solo devolverá los valores que están en ambas matrices. En este punto, si la longitud del conjunto resultante es la misma que el conjunto original, todos los elementos en "set" también están en "check" y, por lo tanto, "set" es un subconjunto de "toCheck"

Nota: Mi solución no funciona si "set" tiene duplicados. No lo voy a cambiar porque no quiero robar los votos de otras personas.

Pista: voté por la respuesta de Cameron.

JaredPar
fuente
44
Esto funciona si de hecho son conjuntos, pero no si el segundo "conjunto" contiene elementos repetidos, ya que realmente es una lista. Es posible que desee utilizar HashSet <double> para asegurarse de que haya configurado la semántica.
tvanfosson
no funciona cuando ambas matrices tienen elementos, que no están en la otra matriz.
da_berni