Ricerca di sequenze di interi

Hmm, posso pensare a due possibili algoritmi: una scansione lineare attraverso la sequenza A o la costruzione di un dizionario con una ricerca costante degli indici.

Se stai testando molte potenziali sottosezioni B contro una singola sequenza più grande A , ti suggerirei di usare la variante con il dizionario.

Scansione lineare

Descrizione

Manteniamo un cursore per la sequenza A . Quindi eseguiamo l'iterazione di tutti gli elementi nella sottosequenza B . Per ogni elemento, spostiamo il cursore in avanti in A fino a quando non abbiamo trovato un oggetto corrispondente. Se non è stato trovato alcun oggetto corrispondente, allora B non è una sottosequenza.

Questo funziona sempre in O (seq.size) .

Pseudocodice

Stile 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

Stile funzionale:

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

Esempio di implementazione (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;

Ricerca dizionario

Descrizione

Mappiamo gli elementi della sequenza A ai loro indici. Quindi cerchiamo indici adatti per ogni elemento in B , saltiamo quegli indici che sono troppo piccoli e selezioniamo l'indice più piccolo possibile come limite inferiore. Quando non vengono trovati indici, allora B non è una sottosequenza.

Esegue qualcosa come O (subseq.size · k) , dove k descrive quanti numeri duplicati ci sono in seq . Più un overhead O (seq.size)

Il vantaggio di questa soluzione è che una decisione negativa può essere raggiunta molto più velocemente (fino a un tempo costante), una volta che hai pagato l'overhead della costruzione della tabella di ricerca.

Pseudocodice:

Stile 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

Stile funzionale:

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

Esempio di implementazione (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 di ricerca del dizionario: codifica come macchina a stati finiti

Descrizione

Possiamo ridurre ulteriormente la complessità algoritmica fino a O (sottoseq.size) se scambiamo più memoria. Invece di mappare gli elementi ai loro indici, creiamo un grafico in cui ogni nodo rappresenta un elemento nel suo indice. I bordi mostrano possibili transizioni, ad es. la sequenza a, b, a avrebbe i bordi a@1 → b@2, a@1 → a@3, b@2 → a@3 . Questo grafico è equivalente a una macchina a stati finiti.

Durante la ricerca manteniamo un cursore che inizialmente è il primo nodo dell'albero. Quindi camminiamo sul bordo per ogni elemento nel sottolista B . Se questo limite non esiste, allora B non è un sottolista. Se dopo tutti gli elementi il cursore contiene un nodo valido, allora B è una sottolista.

Pseudocodice

Stile 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

Stile funzionale:

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

Esempio di implementazione (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;

Ecco un approccio pratico che evita "il duro lavoro" di implementare il tuo algoritmo ed evita anche di "reinventare la ruota": utilizza un espressione regolare motore per il problema.

Basta inserire tutti i numeri di A in una stringa e tutti i numeri di B in una stringa separata dall'espressione regolare (.*) . Aggiungi un carattere ^ all'inizio e $ alla fine. Quindi lascia che il tuo motore di espressioni regolari preferito cerchi tutte le corrispondenze. Ad esempio, quando

A = (1234356), B = (236)

crea un reg exp per B come ^(.*)2(.*)3(.*)6(.*)$ . Ora esegui una ricerca globale delle espressioni regolari. Per scoprire in quali posizioni in A corrisponde la tua sottosequenza, basta controllare la lunghezza dei primi 3 submatch.

Se il tuo intervallo di numeri interi lascia da 0 a 9, puoi prendere in considerazione la possibilità di codificarli prima con lettere singole per farlo funzionare, oppure devi adattare l'idea usando un carattere di separazione.

Naturalmente, la velocità di tale approccio dipenderà molto dalla velocità del motore di reg exp che si sta utilizzando, ma sono disponibili motori altamente ottimizzati, e suppongo che sarà difficile implementare un algoritmo più veloce "su la scatola".

Questo algoritmo dovrebbe essere abbastanza efficiente se ottenere la lunghezza e iterare la sequenza è efficiente.

1. Confronta la lunghezza di entrambe le sequenze. Memorizza il più lungo in sequence e il più corto in subsequence
2. Inizia dall'inizio di entrambe le sequenze e loop fino alla fine di sequence .
   1. È il numero nella posizione corrente di sequence uguale al numero nella posizione corrente di subsequence
   2. Se sì, sposta entrambe le posizioni ulteriormente
   3. In caso contrario, sposta solo la posizione di sequence un'altra
3. È la posizione di subsequence alla fine del sequence
4. Se sì, le due sequenze corrispondono
5. In caso contrario, le due sequenze non corrispondono