Pesquisando Sequências Inteiras

Eu tenho um problema de pesquisa bastante complexo que consegui reduzir para a descrição a seguir. Estou pesquisando no Google, mas não consegui encontrar um algoritmo que pareça se encaixar perfeitamente no meu problema. Em particular, a necessidade de pular números inteiros arbitrários. Talvez alguém aqui possa me indicar alguma coisa?

Tome uma sequência de números inteiros A, por exemplo (1 2 3 4)

Pegue várias seqüências de números inteiros e teste se algum deles corresponde a A tal que.

1. A contém todos os números inteiros na sequência testada
2. A ordem dos números inteiros na sequência testada é a mesma em A
3. Não nos importamos com números inteiros em A que não estejam na sequência de teste
4. Queremos todas as sequências de teste correspondentes, não apenas a primeira.

Um exemplo

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

B corresponde a

C corresponde a

D não corresponde a A, pois a ordem é diferente

E não corresponde a A, pois contém um número inteiro que não está em A

Espero que esta explicação seja clara o suficiente. O melhor que consegui fazer é criar uma árvore das sequências de teste e repetir A. A necessidade de poder pular números inteiros leva a muitos caminhos de pesquisa sem êxito.

obrigado

Lendo algumas sugestões, sinto que preciso esclarecer alguns pontos que deixei muito vagos.

1. Números repetidos são permitidos; de fato, isso é muito importante, pois permite que uma única sequência de teste corresponda a A de várias maneiras

   A = (1234356), B = (236), as correspondências podem ser -23 --- 6 ou -2--3-6

2. Eu espero que exista um número muito grande de seqüências de teste, pelo menos em milhares e a sequência A tenderá a ter um comprimento máximo de talvez 20. Portanto, simplesmente tentar combinar cada sequência de teste uma por uma repetindo a iteração se torna extremamente ineficiente.

Desculpe se isso não estava claro.

Hmm, eu posso pensar em dois possíveis algoritmos: uma varredura linear através da sequência A ou a construção de um dicionário com busca constante dos índices.

Se você estiver testando muitas subsequências potenciais B contra uma única sequência maior A , sugiro que você use a variante com o dicionário.

Digitalização linear

Descrição

Nós manter um cursor para a sequência de um . Em seguida, percorrer todos os itens na subsequence B . Para cada item, movemos o cursor para frente em A até encontrarmos um item correspondente. Se nenhum item correspondente foi encontrado, B não é uma subsequência.

Isso sempre é executado em O (seq.size) .

Pseudo-código

Estilo imperativo:

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

Estilo funcional:

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

Exemplo de implementação (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;

Pesquisa de dicionário

Descrição

Mapeamos os itens da sequência A para seus índices. Em seguida, procuramos índices adequados para cada item em B , pulamos os índices que são pequenos e selecionamos o menor índice possível como limite inferior. Quando nenhum índice for encontrado, então B não é uma subsequência.

É executado em algo como O (subseq.size · k) , onde k descreve quantos números duplicados existem seq. Mais um O (seq.size) sobrecarga

A vantagem desta solução é que uma decisão negativa pode ser alcançada muito mais rapidamente (até o tempo constante), depois que você paga a sobrecarga de criação da tabela de pesquisa.

Pseudo-código:

Estilo imperativo:

# 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

Estilo funcional:

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

Exemplo de implementação (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;

Variante de pesquisa de dicionário: Codificação como uma máquina de estados finitos

Descrição

Podemos reduzir ainda mais a complexidade algorítmica para O (subseq.size) se trocarmos mais memória. Em vez de mapear elementos para seus índices, criamos um gráfico em que cada nó representa um elemento em seu índice. As arestas mostram possíveis transições, por exemplo, a sequência a, b, ateria as arestas a@1 → b@2, a@1 → a@3, b@2 → a@3. Este gráfico é equivalente a uma máquina de estados finitos.

Durante a pesquisa, mantemos um cursor que inicialmente é o primeiro nó da árvore. Em seguida, caminhar à beira de cada elemento na sublista B . Se não existir essa aresta, B não será uma sub-lista. Se após todos os elementos o cursor contiver um nó válido, B será uma sub-lista.

Pseudo-código

Estilo imperativo:

# 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

Estilo funcional:

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

Exemplo de implementação (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;

Aqui está uma abordagem prática que evita "o trabalho duro" de implementar seu próprio algoritmo e também evita "reinventar a roda": utilize uma expressão regular mecanismo de para o problema.

Basta colocar todos os números de A em uma sequência e todos os números de B em uma sequência separados pela expressão regular (.*). Adicione um ^personagem no início e$ no final. Em seguida, deixe seu mecanismo de expressão regular favorito procurar todas as correspondências. Por exemplo, quando

A = (1234356), B = (236)

criar um exp exp para B como ^(.*)2(.*)3(.*)6(.*)$ . Agora execute uma pesquisa global regexp. Para descobrir em quais posições A sua correspondência subsequente, basta verificar o comprimento das 3 primeiras sub-correspondências.

Se o seu intervalo de números inteiros deixar de 0 a 9, considere codificá-los com uma única letra primeiro para que isso funcione, ou será necessário adaptar a ideia usando um caractere de separação.

Obviamente, a velocidade dessa abordagem dependerá muito da velocidade do mecanismo reg exp que você está usando, mas existem mecanismos altamente otimizados disponíveis, e acho que será difícil implementar um algoritmo mais rápido "pronto para uso" .

Esse algoritmo deve ser bastante eficiente se obter o comprimento e iterar a sequência for eficiente.

1. Compare o comprimento das duas seqüências. Armazene quanto mais tempo sequencee quanto menorsubsequence
2. Comece no início de ambas as seqüências e faça um loop até o final de sequence.
   1. O número na posição atual é sequenceigual ao número na posição atual desubsequence
   2. Se sim, mova as duas posições mais uma
   3. Caso contrário, mova apenas a posição de sequencemais uma
3. A posição de subsequenceno final dosequence
4. Se sim, as duas sequências correspondem
5. Caso contrário, as duas sequências não coincidem