Проверьте, является ли массив подмножеством другого

145

Любая идея о том, как проверить, является ли этот список подмножеством другого?

В частности, у меня есть

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

Как проверить, что t2 является подмножеством t1, используя LINQ?

Гравитон
источник
Если списки отсортированы (как в вашем примере), это должно быть возможно за O (n + m) времени.
полковник Паник

Ответы:

255
bool isSubset = !t2.Except(t1).Any();
Кэмерон МакФарланд
источник
1
Я создал метод расширения geekswithblogs.net/mnf/archive/2011/05/13/…
Майкл Фрейдгейм
@Bul Ikana Работа с этим кодом проста, метод расширения внутренне вызывает Equals и GetHashCode переопределенных методов класса объекта, если для задания не предусмотрен IEqualityComparer.
Мринал Камбой
2
Если списки имеют длину n и m, какова временная сложность этого алгоритма?
полковник Паник
2
Было бы неплохо, если бы все сводилось к методу linq, который называется ContainsAll
Себастьян Паттен,
60

Используйте HashSet вместо List, если работаете с наборами. Тогда вы можете просто использовать IsSubsetOf ()

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

bool isSubset = t2.IsSubsetOf(t1);

Извините, что он не использует LINQ. :-(

Если вам нужно использовать списки, то решение @ Jared работает с предупреждением о том, что вам нужно будет удалить все повторяющиеся элементы, которые существуют.

tvanfosson
источник
3
Именно. Вы хотите установить операцию, используйте класс, предназначенный для них. Решение Кэмерона креативно, но не так ясно / выразительно, как HashSet.
технофил
2
Хм, я не согласен, потому что в вопросе конкретно сказано: «используйте LINQ».
JaredPar
9
@JaredPar: И что? Разве не лучше показать кому-то правильный путь, чем тот, которым он хочет идти?
Джонатан Аллен
Список поддерживает свой порядок, а набор - нет. Если порядок важен, это даст неверные результаты.
UuDdLrLrSs
11

Если вы проводите модульное тестирование, вы также можете использовать метод CollectionAssert.IsSubsetOf :

CollectionAssert.IsSubsetOf(subset, superset);

В приведенном выше случае это будет означать:

CollectionAssert.IsSubsetOf(t2, t1);
Геза
источник
7

Это значительно более эффективное решение, чем другие, размещенные здесь, особенно топовое решение:

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

Если вы можете найти один элемент в t2, которого нет в t1, то вы знаете, что t2 не является подмножеством t1. Преимущество этого метода в том, что он выполняется на месте, без выделения дополнительного пространства, в отличие от решений, использующих .Except или .Intersect. Кроме того, это решение может сломаться, как только оно найдет один элемент, который нарушает условие подмножества, в то время как другие продолжают поиск. Ниже приведена оптимальная длинная форма решения, которая в моих тестах лишь незначительно быстрее, чем приведенное выше сокращенное решение.

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

Я сделал некоторый элементарный анализ производительности всех решений, и результаты были радикальными. Эти два решения примерно в 100 раз быстрее, чем решения .Except () и .Intersect (), и не используют дополнительную память.

user2325458
источник
Это именно то, что !t2.Except(t1).Any()делает. Линк работает вперед и назад. Any()спрашивает, есть IEnumerableли хотя бы один элемент. В этом сценарии t2.Except(t1)испускается только первый элемент, t2которого нет в t1. Если первый элемент t2не находится в t1нем, он заканчивается быстрее всего, если все элементы t2находятся в t1нем, он работает дольше всего.
до
В то время как играть с каким - то ориентиром, я узнал, когда вы берете t1={1,2,3,...9999}и t2={9999,9998,99997...9000}, вы получаете следующие измерения: !t2.Except(t1).Any(): 1ms -> t2.All(e => t1.Contains(e)): 702ms. И чем хуже диапазон, тем хуже.
апреля
2
Это не так, как работает Linq. t2.Except (t1)возвращается IEnumerableне собой Collection. Он испускает все возможные элементы, только если вы перебираете его полностью, например, с помощью ToArray ()или ToList ()или используете foreachбез разрыва внутри. Найдите отложенное выполнение linq, чтобы узнать больше об этой концепции.
до
1
Я полностью осознаю, как отложенное выполнение работает в Linq. Вы можете отложить выполнение всего, что хотите, но когда вы хотите определить, является ли t2 подмножеством t1, вам нужно будет перебрать весь список, чтобы выяснить это. Нельзя обойти этот факт.
user2325458
2
Давайте возьмем пример из вашего комментария t2={1,2,3,4,5,6,7,8} t1={2,4,6,8} t2.Except(t1)=> первый элемент t2 = 1 => разница от 1 до t1 равна 1 (проверено по {2,4,6,8}) => Except()испускает первый элемент 1 => Any()получает элемент => Any()приводит к true => нет дальнейшей проверки элементов в t2.
до
6

Решение Кэмерона в качестве метода расширения:

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

Использование:

bool isSubset = t2.IsSubsetOf(t1);

(Это похоже, но не совсем то, что опубликовано в блоге @ Michael)

Нил
источник
0

Основываясь на ответах @Cameron и @Neil, я написал метод расширения, использующий ту же терминологию, что и класс 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
источник
0

Здесь мы проверяем, что если есть какой-либо элемент в дочернем списке (то есть t2), который не содержится в родительском списке (то есть t1). Если ни один из них не существует, то список является подмножеством другого

например:

bool isSubset = !(t2.Any(x => !t1.Contains(x)));
Люцифер
источник
-1

Попробуй это

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

Идея в том, что Intersect будет возвращать только те значения, которые есть в обоих массивах. В этот момент, если длина результирующего набора совпадает с исходным набором, тогда все элементы в «наборе» также находятся в «проверке», и, следовательно, «набор» является подмножеством «toCheck»

Примечание. Мое решение не работает, если в «множестве» есть дубликаты. Я не изменяю это, потому что я не хочу красть голоса других людей.

Подсказка: я голосовал за ответ Кэмерон.

JaredPar
источник
4
Это работает, если они действительно являются наборами, но не если второй «набор» содержит повторяющиеся элементы, поскольку это действительно список. Возможно, вы захотите использовать HashSet <double>, чтобы убедиться, что он установил семантику.
tvanfosson
не работает, когда оба массива имеют элементы, которых нет в другом массиве.
da_berni