Что такое эффективный способ определить, является ли список подмножеством другого списка?
Пример:
is_subset(List(1,2,3,4),List(2,3)) //Returns true
is_subset(List(1,2,3,4),List(3,4,5)) //Returns false
Я в основном ищу эффективный алгоритм и не слишком беспокоюсь о том, как хранится список. Он может храниться в массиве, списке ссылок или другой структуре данных.
Спасибо
EDIT: список отсортирован
Вот несколько компромиссов, которые вы можете сделать. Предположим, что у вас есть два набора элементов, 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.
Сложность времени: about O ( | S | Log | S | + | T | Log | T | ), чтобы создать отсортированный списки, O ( max (| S |, | T |) ) для сравнения.
Сложная сложность: about O ( | S | + | T | )
Пример (С++)
#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 | )
Пример (С++)
#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 | )
Пример: (С++)
#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 filter - это фантастический набор битов. Обязательно выберите размер фильтра и хэш-функции.
Алгоритм (эскиз): Инициализировать битсет до 0. Чтобы добавить элемент в фильтр цветения, хешируйте его с каждой хэш-функцией и установите соответствующий бит в битете. Определение включения работает так же, как для битов.
Сложность времени: O ( размер фильтра )
Сложность пространства: O ( размер фильтра )
Вероятность правильности: всегда правильно, если она отвечает за "S не включает T". Что-то вроде 0.6185 ^ (| S | x | T |/(filter size))), если он отвечает "S включает T". В частности, размер фильтра должен быть пропорционален произведению | S | и | T | чтобы дать разумную вероятность точности.
Для С++ лучшим способом является использование алгоритма 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)
Если оба списка упорядочены, одним простым решением будет одновременное переключение обоих списков (с двумя указателями на указатели в обоих списках) и убедитесь, что все элементы во втором списке отображаются в первом списке (пока все элементы найдены или пока вы не достигнете большего числа в первом списке).
Псевдокод в С++ будет выглядеть примерно так:
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. Это способ С++, я думаю, что это будет сделано.
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