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

Эффективный алгоритм использует своего рода конечный автомат, где вы храните принимающие состояния в памяти (в 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

РЕДАКТИРОВАТЬ: конечно, если список отсортирован, вы не нужен этот алгоритм, просто сделайте:

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

Вот несколько компромиссов, которые вы можете сделать. Предположим, у вас есть два набора элементов, 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 + -дерево), которое можно перебирать в постоянном пространстве.

Алгоритм : Для каждого элемента в 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 проверьте, не s в хеш-таблице.

Временная сложность : 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. Фильтры Блума
Все преимущества битовых наборов в скорости без досадных ограничений на размер вселенной, которые есть у битовых наборов. Только один недостаток: они иногда (часто, если вы не будете осторожны) дают неправильный ответ: если алгоритм говорит «нет», то у вас определенно нет включения. Если алгоритм говорит «да», вы можете или не можете. Лучшая точность достигается за счет выбора фильтра большого размера, и хорошие хэш-функции.

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

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

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

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

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

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

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

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

Описание:

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

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

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;
    }
}

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

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

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

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

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

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

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

В любом случае, подпоследовательность - это просто проблема с подстрокой. Оптимальные алгоритмы включают Кнута-Морриса-Пратта и Бойера-Мура, а также несколько более сложных.

Если вы действительно имели в виду подмножество, и, следовательно, вы говорите о множествах, а не списках, вы можете просто использовать 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)
}

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

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

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

Псевдокод в 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;

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

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

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

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

return set(list2).issubset(list1)

Или:

return set(list2) <= set(list1)

Для indexOfSeq в магистрали scala я реализовал KMP, который вы можете проверить: SequenceTemplate

Для 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());

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