Поиск целочисленных последовательностей

У меня довольно сложная проблема поиска, которую мне удалось свести к следующему описанию. Я гуглил, но не смог найти алгоритм, который, кажется, полностью соответствует моей проблеме. В частности, необходимо пропустить произвольные целые числа. Может быть, кто-то здесь может указать мне на что-то?

Возьмем последовательность целых чисел A, например (1 2 3 4)

Возьмите различные последовательности целых чисел и проверьте, совпадает ли любая из них с A, что.

1. A содержит все целые числа в проверенной последовательности
2. Порядок целых чисел в тестируемой последовательности одинаков в A
3. Нам нет дела до целых чисел в A, которых нет в тестовой последовательности
4. Нам нужны все соответствующие тестовые последовательности, а не только первая.

Пример

A = (1 2 3 4)
B = (1 3)
C = (1 3 4)
D = (3 1)
E = (1 2 5)

B соответствует A

С соответствует А

D не соответствует A, так как порядок отличается

E не соответствует A, так как содержит целое число, не входящее в A

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

Благодарность

Читая некоторые предложения, я чувствую, что должен уточнить пару моментов, которые я оставил слишком расплывчатыми.

1. Допускаются повторные числа, на самом деле это очень важно, так как позволяет одной тестовой последовательности соответствовать A несколькими способами

   A = (1234356), B = (236), совпадения могут быть либо -23 --- 6, либо -2--3-6.

2. Я ожидаю, что будет очень большое количество тестовых последовательностей, по крайней мере, тысяч, и последовательность A будет иметь максимальную длину, может быть, 20. Таким образом, простая попытка сопоставить каждую тестовую последовательность одну за другой путем итерации становится крайне неэффективной.

Извините, если это не было ясно.

Хм, я могу вспомнить два возможных алгоритма: линейное сканирование последовательности A или построение словаря с постоянным поиском индексов.

Если вы тестируете много потенциальных подпоследовательностей B против одной большой последовательности A , я бы посоветовал вам использовать вариант со словарем.

Линейное сканирование

Описание

Мы поддерживаем курсор для последовательности A . Затем мы перебираем все элементы в подпоследовательности B . Для каждого элемента мы перемещаем курсор вперед по A, пока не найдем соответствующий элемент. Если соответствующий элемент не был найден, то B не является подпоследовательностью.

Это всегда работает в O (seq.size) .

ПСЕВДОКОД

Императивный стиль:

def subsequence? seq, subseq:
  i = 0
  for item in subseq:
    i++ while i < seq.size and item != seq[i]
    return false if i == seq.size
  return true

Функциональный стиль:

let rec subsequence? = function
| _ [] -> true
| [] _ -> false
| cursor::seq item::subseq ->
  if   cursor = item
  then subsequence? seq subseq
  else subsequence? seq item::subseq

Пример реализации (Perl):

use strict; use warnings; use signatures; use Test::More;

sub is_subsequence_i ($seq, $subseq) {
  my $i = 0;
  for my $item (@$subseq) {
    $i++ while $i < @$seq and $item != $seq->[$i];
    return 0 if $i == @$seq;
  }
  return 1;
}

sub is_subsequence_f ($seq, $subseq) {
  return 1 if @$subseq == 0;
  return 0 if @$seq == 0;
  my ($cursor, @seq) = @$seq;
  my ($item, @subseq) = @$subseq;
  return is_subsequence_f(\@seq, $cursor == $item ? \@subseq : $subseq);
}

my $A = [1, 2, 3, 4];
my $B = [1, 3];
my $C = [1, 3, 4];
my $D = [3, 1];
my $E = [1, 2, 5];

for my $is_subsequence (\&is_subsequence_i, \&is_subsequence_f) {
  ok $is_subsequence->($A, $B), 'B in A';
  ok $is_subsequence->($A, $C), 'C in A';
  ok ! $is_subsequence->($A, $D), 'D not in A';
  ok ! $is_subsequence->($A, $E), 'E not in A';
  ok $is_subsequence->([1, 2, 3, 4, 3, 5, 6], [2, 3, 6]), 'multiple nums';
}

done_testing;

Поиск по словарю

Описание

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

Работает в чем-то вроде O (subseq.size · k) , где k описывает, сколько в них повторяющихся чисел seq. Плюс O (seq.size) накладные расходы

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

псевдокод:

Императивный стиль:

# preparing the lookup table
dict = {}
for i, x in seq:
  if exists dict[x]:
    dict[x].append(i)
  else:
    dict[x] = [i]

def subsequence? subseq:
  min_index = -1
  for x in subseq:
    if indices = dict[x]:
      suitable_indices = indices.filter(_ > min_index)
      return false if suitable_indices.empty?
      min_index = suitable_indices[0]
    else:
      return false
  return true

Функциональный стиль:

let subsequence? subseq =
  let rec subseq-loop = function
  | [] _ -> true
  | x::subseq min-index ->
    match (map (filter (_ > min-index)) data[x])
    | None -> false
    | Some([]) -> false
    | Some(new-min::_) -> subseq-loop subseq new-min
  in
    subseq-loop subseq -1

Пример реализации (Perl):

use strict; use warnings; use signatures; use Test::More;

sub build_dict ($seq) {
  my %dict;
  while (my ($i, $x) = each @$seq) {
    push @{ $dict{$x} }, $i;
  }
  return \%dict;
}

sub is_subsequence_i ($seq, $subseq) {
  my $min_index = -1;
  my $dict = build_dict($seq);
  for my $x (@$subseq) {
    my $indices = $dict->{$x} or return 0;
    ($min_index) = grep { $_ > $min_index } @$indices or return 0;
  }
  return 1;
}

sub is_subsequence_f ($seq, $subseq) {
  my $dict = build_dict($seq);
  use feature 'current_sub';
  return sub ($subseq, $min_index) {
    return 1 if @$subseq == 0;
    my ($x, @subseq) = @$subseq;
    my ($new_min) = grep { $_ > $min_index } @{ $dict->{$x} // [] } or return 0;
    __SUB__->(\@subseq, $new_min);
  }->($subseq, -1);
}

my $A = [1, 2, 3, 4];
my $B = [1, 3];
my $C = [1, 3, 4];
my $D = [3, 1];
my $E = [1, 2, 5];

for my $is_subsequence (\&is_subsequence_i, \&is_subsequence_f) {
  ok $is_subsequence->($A, $B), 'B in A';
  ok $is_subsequence->($A, $C), 'C in A';
  ok ! $is_subsequence->($A, $D), 'D not in A';
  ok ! $is_subsequence->($A, $E), 'E not in A';
  ok $is_subsequence->([1, 2, 3, 4, 3, 5, 6], [2, 3, 6]), 'multiple nums';
}

done_testing;

Вариант поиска по словарю: кодирование как конечный автомат

Описание

Мы можем еще больше уменьшить алгоритмическую сложность до O (subseq.size), если будем торговать большим объемом памяти. Вместо того, чтобы сопоставлять элементы с их индексами, мы создаем график, где каждый узел представляет элемент в своем индексе. Ребра показывают возможные переходы, например, последовательность a, b, aбудет иметь ребра a@1 → b@2, a@1 → a@3, b@2 → a@3. Этот граф эквивалентен конечному автомату.

Во время поиска мы поддерживаем курсор, который изначально является первым узлом дерева. Затем мы ходить края для каждого элемента в Подсписок B . Если такого ребра не существует, то B не является подсписком. Если после всех элементов курсор содержит действительный узел, то B является подсписком.

ПСЕВДОКОД

Императивный стиль:

# preparing the graph
graph = {}
for x in seq.reverse:
  next_graph = graph.clone
  next_graph[x] = graph
  graph = next_graph

def subseq? subseq:
  cursor = graph
  for x in subseq:
    cursor = graph[x]
    return false if graph == null
  return true

Функциональный стиль:

let subseq? subseq =
  let rec subseq-loop = function
  | [] _ -> true
  | x::subseq graph -> match (graph[x])
    | None -> false
    | Some(next-graph) -> subseq-loop subseq next-graph
  in
    subseq-loop subseq graph

Пример реализации (Perl):

use strict; use warnings; use signatures; use Test::More;

sub build_graph ($seq) {
  my $graph = {};
  for (reverse @$seq) {
    $graph = { %$graph, $_ => $graph };
  }
  return $graph;
}

sub is_subsequence_i ($seq, $subseq) {
  my $cursor = build_graph($seq);
  for my $x (@$subseq) {
    $cursor = $cursor->{$x} or return 0;
  }
  return 1;
}

sub is_subsequence_f ($seq, $subseq) {
  my $graph = build_graph($seq);
  use feature 'current_sub';
  return sub ($subseq, $graph) {
    return 1 if @$subseq == 0;
    my ($x, @subseq) = @$subseq;
    my $next_graph = $graph->{$x} or return 0;
    __SUB__->(\@subseq, $next_graph);
  }->($subseq, $graph);
}

my $A = [1, 2, 3, 4];
my $B = [1, 3];
my $C = [1, 3, 4];
my $D = [3, 1];
my $E = [1, 2, 5];

for my $is_subsequence (\&is_subsequence_i, \&is_subsequence_f) {
  ok $is_subsequence->($A, $B), 'B in A';
  ok $is_subsequence->($A, $C), 'C in A';
  ok ! $is_subsequence->($A, $D), 'D not in A';
  ok ! $is_subsequence->($A, $E), 'E not in A';
  ok $is_subsequence->([1, 2, 3, 4, 3, 5, 6], [2, 3, 6]), 'multiple nums';
}

done_testing;

Вот практический подход, который избегает «тяжелой работы» по реализации собственного алгоритма, а также избегает «изобретать колесо»: использовать механизм регулярных выражений для решения проблемы.

Просто поместите все числа A в строку, а все числа B в строку, разделенные регулярным выражением (.*). Добавьте ^символ в начале и $в конце. Тогда пусть ваш любимый движок регулярных выражений ищет все совпадения. Например, когда

A = (1234356), B = (236)

создать reg exp для B как ^(.*)2(.*)3(.*)6(.*)$. Теперь запустите глобальный поиск по регулярному выражению. Чтобы выяснить, в каких позициях в A соответствует ваша подпоследовательность, просто проверьте длину первых 3 подсовпадений.

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

Конечно, скорость этого подхода будет во многом зависеть от скорости используемого вами механизма reg exp, но есть высоко оптимизированные доступные движки, и я думаю, что будет сложно реализовать более быстрый алгоритм «из коробки» ,

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

1. Сравните длину обеих последовательностей. Храните дольше sequenceи корочеsubsequence
2. Начните с начала обеих последовательностей и продолжайте цикл до конца sequence.
   1. Число в текущей позиции sequenceравно числу в текущей позицииsubsequence
   2. Если да, переместите обе позиции на одну позицию дальше
   3. Если нет, сдвиньте только позицию еще на sequenceодин
3. Является ли положение subsequenceв концеsequence
4. Если да, две последовательности совпадают
5. Если нет, две последовательности не совпадают