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

Вот несколько компромиссов, которые вы можете сделать. Предположим, что у вас есть два набора элементов S и T, взятые из юниверса U. Мы хотим определить, является ли S≥T. В одном из приведенных примеров мы имеем

S = {1,2,3,4}
Т = {3,4,5}
U = {1,2,3,4,5}

1. Сортированные списки (или сбалансированное дерево поиска)
Метод, предложенный большинством плакатов. Если у вас уже есть отсортированные списки или не заботятся о длительности времени, необходимого для их создания (скажем, вы этого не делаете часто), то этот алгоритм в основном представляет собой линейное время и пространство. Обычно это лучший вариант.

(Чтобы быть справедливым в отношении других вариантов здесь, границы времени и пространства должны фактически содержать факторы «Log | U |» в соответствующих местах, но это обычно не является релевантным)

Структуры данных : Сортированный список для каждого из S и T. Или сбалансированное дерево поиска (например, дерево AVL, красно-черное дерево, B + -tree), которые можно повторить в постоянном пространстве.

Алгоритм . Для каждого элемента в T, в порядке, поиск S линейно для этого элемента. Помните, где вы остановились на каждом поиске, и начните следующий поиск там. Если каждый поиск завершен, тогда S≥T.

Сложность времени : около O ( | S | Log | S | + | T | Log | T | ) для создания отсортированных списков, O ( max (| S |, | T |) ) для сравнения.

Сложность пространства : около O ( | S | + | T | )

Пример (C ++)

 #include <set> #include <algorithm> std::set<int> create_S() { std::set<int> S; // note: std::set will put these in order internally S.insert(3); S.insert(2); S.insert(4); S.insert(1); return S; } std::set<int> create_T() { std::set<int> T; // note std::set will put these in order internally T.insert(4); T.insert(3); T.insert(5); return T; } int main() { std::set<int> S=create_S(); std::set<int> T=create_T(); return std::includes(S.begin(),S.end(), T.begin(), T.end()); } 

2. Хэш-таблицы
Лучшая усредненная временная сложность, чем при сортированном списке, может быть получена с использованием хеш-таблиц. Улучшенное поведение для больших наборов происходит за счет, как правило, более низкой производительности для небольших наборов.

Как и в отсортированных списках, я игнорирую сложность, связанную с размером Вселенной.

Структура данных : Хэш-таблица для S, что-то быстро повторяемое для T.

Алгоритм : Вставьте каждый элемент S в свою хэш-таблицу. Затем для каждого элемента из T проверьте, находится ли он в хеш-таблице.

Сложность времени : O ( | S | + | T | ) для настройки, O ( | T | ) для сравнения.

Сложность пространства : O ( | S | + | T | )

Пример (C ++)

 #include <tr1/unordered_set> std::tr1::unordered_set<int> create_S() { std::tr1::unordered_set<int> S; S.insert(3); S.insert(2); S.insert(4); S.insert(1); return S; } std::tr1::unordered_set<int> create_T() { std::tr1::unordered_set<int> T; T.insert(4); T.insert(3); T.insert(5); return T; } bool includes(const std::tr1::unordered_set<int>& S, const std::tr1::unordered_set<int>& T) { for (std::tr1::unordered_set<int>::const_iterator iter=T.begin(); iter!=T.end(); ++iter) { if (S.find(*iter)==S.end()) { return false; } } return true; } int main() { std::tr1::unordered_set<int> S=create_S(); std::tr1::unordered_set<int> T=create_T(); return includes(S,T); } 

3. Бит-множества
Если ваш юниверс особенно мал (допустим, вы можете иметь только элементы 0-32), тогда бит-бит является разумным решением. Время работы (опять же, если вы не заботитесь о времени установки), по существу, является постоянным. В случае, если вы заботитесь о настройке, это все же быстрее, чем создание отсортированного списка.

К сожалению, битеты становятся громоздкими очень быстро для даже юниверса умеренного размера.

Структура данных : бит-вектор (обычно целое число) для каждого из S и T. В данном примере мы могли бы кодировать S = 11110 и T = 00111.

Алгоритм . Вычислите пересечение путем вычисления побитового «и» каждого бита в S с соответствующим битом в T. Если результат равен T, то S≥T.

Сложность времени : O ( | U | + | S | + | T | ) для настройки, O ( | U | ) для сравнения.

Сложность пространства : O ( | U | )

Пример: (C ++)

 #include <bitset> // bitset universe always starts at 0, so create size 6 bitsets for demonstration. // U={0,1,2,3,4,5} std::bitset<6> create_S() { std::bitset<6> S; // Note: bitsets don't care about order S.set(3); S.set(2); S.set(4); S.set(1); return S; } std::bitset<6> create_T() { std::bitset<6> T; // Note: bitsets don't care about order T.set(4); T.set(3); T.set(5); return T; } int main() { std::bitset<6> S=create_S(); std::bitset<6> T=create_T(); return S & T == T; } 

4. Цветные фильтры
Все преимущества скорости битов, без жестких ограничений на размер юниверса, есть у битов. Только одна нижняя сторона: они иногда (часто, если не осторожны) дают неправильный ответ: если алгоритм говорит «нет», то у вас определенно нет включения. Если алгоритм говорит «да», вы можете или нет. Лучшая точность достигается путем выбора большого размера фильтра и хороших хеш-функций.

Учитывая, что они могут и будут давать неправильные ответы, фильтры Bloom могут звучать как ужасная идея. Однако они имеют определенное применение. Как правило, можно использовать фильтры Bloom для быстрого выполнения многих проверок включения, а затем использовать более медленный детерминированный метод, чтобы гарантировать правильность, когда это необходимо. Связанная статья Википедии упоминает некоторые приложения с использованием фильтров Bloom.

Структура данных : фильтр Bloom – это фантастический битрейт. Необходимо заранее выбрать размер фильтра и хэш-функции.

Алгоритм (эскиз): Инициализация битового набора до 0. Чтобы добавить элемент в фильтр цветения, хешируйте его с каждой хеш-функцией и установите соответствующий бит в битете. Определение включения работает так же, как для битов.

Сложность времени : O ( размер фильтра )

Сложность пространства : O ( размер фильтра )

Вероятность правильности : всегда правильно, если она отвечает за «S не включает T». Что-то вроде 0,6185 ^ (| S | x | T | / ( размер фильтра ))), если он отвечает «S включает T». В частности, размер фильтра должен быть пропорционален произведению | S | и | T | чтобы дать разумную вероятность точности.

Для C ++ лучшим способом является использование алгоритма std::includes :

 #include <algorithm> std::list<int> l1, l2; ... // Test whether l2 is a subset of l1 bool is_subset = std::includes(l1.begin(), l1.end(), l2.begin(), l2.end()); 

Это требует, чтобы оба списка сортировались, как указано в вашем вопросе. Сложность линейна.

Просто хотел упомянуть, что у Python есть метод для этого:

 return set(list2).issubset(list1) 

Или:

 return set(list2) <= set(list1) 

Если оба списка упорядочены, одним простым решением будет одновременное переключение обоих списков (с двумя указателями рельефа в обоих списках) и убедитесь, что все элементы во втором списке отображаются в первом списке (пока не будут найдены все элементы , или пока вы не достигнете большего числа в первом списке).

Псевдокод в C ++ будет выглядеть примерно так:

 List l1, l2; iterator i1 = l1.start(); iterator i2 = l2.start(); while(i1 != l1.end() && i2 != l2.end()) { if (*i1 == *i2) { i1++; i2++; } else if (*i1 > *i2) { return false; } else { i1++; } } return true; 

(Очевидно, что это не сработает, но идея должна быть ясной).

Если списки не упорядочены, вы можете использовать хеш-таблицу – вставить все свои элементы в первый список, а затем проверить, отображаются ли все элементы во втором списке в хэш-таблице.

Это алгоритмические ответы. На разных языках существуют встроенные методы по умолчанию, чтобы проверить это.

Если вас беспокоит порядок или непрерывность, вам может потребоваться использовать алгоритм Boyer-Moore или Horspool .

Вопрос в том, хотите ли вы считать [2, 1] подмножеством [1, 2, 3]? Вы хотите, чтобы [1, 3] считались подмножеством [1, 2, 3]? Если ответ не соответствует обоим из них, вы можете рассмотреть один из связанных с ним алгоритмов. В противном случае вы можете рассмотреть хэш-набор.

Scala, предполагая, что вы имеете в виду подпоследовательность подмножеством:

 def is_subset[A,B](l1: List[A], l2: List[B]): Boolean = (l1 indexOfSeq l2) > 0 

Во всяком случае, подпоследовательность – это просто проблема подстроки. Оптимальные алгоритмы включают Knuth-Morris-Pratt и Boyer-Moore, а также несколько более сложных.

Если вы действительно имели в виду подмножество, и, следовательно, вы говорите о наборах, а не о списках, вы можете просто использовать метод subsetOf в Scala. Алгоритмы будут зависеть от того, как хранится набор. Следующий алгоритм работает для хранения списка, что является очень субоптимальным.

 def is_subset[A,B](l1: List[A], l2: List[B]): Boolean = (l1, l2) match { case (_, Nil) => true case (Nil, _) => false case (h1 :: t1, h2 :: t2) if h1 == h2 => is_subset(t1, t2) case (_ :: tail, list) => is_subset(tail, list) } 

Для indexOfSeq в scala trunk я реализовал KMP, который вы можете изучить: SequenceTemplate

Если вы согласны с хранением данных в хэшсе, вы можете просто проверить, содержит ли list1 x для каждого x в списке2. Которая будет близка к O (n) в размере списка2. (Конечно, вы также можете сделать то же самое с другими структурами данных, но это приведет к разным временам работы).

Это сильно зависит от языка / инструментария, а также от размера и хранения списков.

Если списки отсортированы, один цикл может определить это. Вы можете просто начать большой список, пытаясь найти первый элемент меньшего списка (перерыв, если вы передадите его по значению), затем перейдите к следующему и продолжайте с текущего местоположения. Это быстро, так как это алгоритм с одним циклом / одним проходом.

Для несортированных списков чаще всего создается некоторая форма хеш-таблицы из элементов первого списка, а затем выполняется поиск каждого элемента во втором списке из хэша. Это подход, который многие из расширений .NET LINQ используют внутри для поиска элементов в списке и достаточно хорошо масштабируются (хотя они имеют довольно большие требования к временной памяти).

 func isSubset ( @list, @possibleSubsetList ) { if ( size ( @possibleSubsetList ) > size ( @list ) ) { return false; } for ( @list : $a ) { if ( $a != @possibleSubsetList[0] ) { next; } else { pop ( @possibleSubsetList ); } } if ( size ( @possibleSubsetList ) == 0 ) { return true; } else { return false; } } 

O (n) альт. конечно, isSubset ((1,2,3,4,5), (2,4)) вернет true

Вы должны взглянуть на реализацию поиска метода STL. Я думаю, что это будет C ++.

http://www.sgi.com/tech/stl/search.html

Описание:

Поиск находит подпоследовательность в диапазоне [first1, last1), которая идентична [first2, last2] при сравнении по элементам.

Вы можете увидеть проблему, чтобы проверить, является ли список подмножеством другого списка в качестве той же самой проблемы, чтобы проверить, принадлежит ли подстрока строке. Наиболее известным алгоритмом для этого является KMP (Knuth-Morris-Pratt). Посмотрите на wikipedia для псевдокода или просто используйте какой-либо метод String.contains, доступный на выбранном вами языке. знак равно

Эффективный алгоритм использует какой-то государственный автомат, в котором вы сохраняете принимающие состояния в памяти (в python):

 def is_subset(l1, l2): matches = [] for e in l1: # increment to_check = [0] + [i+1 for i in matches] matches = [] # nothing matches for i in to_check: if l2[i] = e: if i == len(l2)-1: return True matches.append(i) return False 

EDIT: конечно, если список отсортирован, вам не нужен этот алгоритм, просто выполните:

 def is_subset(l1, l2): index = 0 for e in l1: if e > l2[index]: return False elif e == l2[index]: index += 1 else: index == 0 if index == len(l2): return True return False