Recherche de séquences entières

J'ai un problème de recherche assez complexe que j'ai réussi à réduire à la description suivante. J'ai fait des recherches sur Google, mais je n'ai pas pu trouver d'algorithme qui semble convenir parfaitement à mon problème. En particulier, la nécessité de sauter des entiers arbitraires. Peut-être que quelqu'un ici peut me montrer quelque chose?

Prenez une séquence d'entiers A, par exemple (1 2 3 4)

Prenez différentes séquences d'entiers et testez si l'un d'eux correspond à A tel que.

1. A contient tous les entiers de la séquence testée
2. L'ordre des entiers dans la séquence testée est le même dans A
3. Nous ne nous soucions pas des entiers dans A qui ne sont pas dans la séquence de test
4. Nous voulons toutes les séquences de test correspondantes, pas seulement la première.

Un exemple

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

B correspond à A

C correspond à A

D ne correspond pas à A car la commande est différente

E ne correspond pas à A car il contient un entier qui n'est pas dans A

J'espère que cette explication est suffisamment claire. Le mieux que j'ai réussi à faire est de construire un arbre des séquences de test et d'itérer sur A. La nécessité de pouvoir ignorer les entiers conduit à de nombreux chemins de recherche infructueux.

Merci

En lisant certaines suggestions, j'estime devoir clarifier quelques points que j'ai laissés trop vagues.

1. Les nombres répétés sont autorisés, en fait, c'est assez important car cela permet à une seule séquence de test de correspondre à A de plusieurs façons

   A = (1234356), B = (236), les correspondances peuvent être -23 --- 6 ou -2--3-6

2. Je m'attends à ce qu'il y ait un très grand nombre de séquences de test, au moins des milliers et la séquence A aura tendance à avoir une longueur maximale de peut-être 20. Ainsi, simplement essayer de faire correspondre chaque séquence de test une par une en itérant devient extrêmement inefficace.

Désolé si ce n'était pas clair.

Hmm, je peux penser à deux algorithmes possibles: un balayage linéaire à travers la séquence A , ou la construction d'un dictionnaire avec une recherche en temps constant des indices.

Si vous testez de nombreuses sous-séquences B potentielles contre une seule séquence A plus grande , je vous suggère d'utiliser la variante avec le dictionnaire.

Balayage linéaire

La description

Nous maintenons un curseur pour la séquence A . Ensuite , nous parcourons tous les articles dans la sous- séquence B . Pour chaque élément, nous déplaçons le curseur vers l'avant dans A jusqu'à ce que nous ayons trouvé un élément correspondant. Si aucun élément correspondant n'a été trouvé, alors B n'est pas une sous-séquence.

Cela s'exécute toujours en O (taille suivante) .

Pseudocode

Style impératif:

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

Style fonctionnel:

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

Exemple d'implémentation (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;

Recherche dans le dictionnaire

La description

Nous mappons les éléments de la séquence A à leurs indices. Ensuite, nous recherchons des indices appropriés pour chaque élément de B , ignorons les indices trop petits et choisissons le plus petit indice possible comme limite inférieure. Quand aucun indice n'est trouvé, alors B n'est pas une sous-séquence.

Fonctionne dans quelque chose comme O (subseq.size · k) , où k décrit le nombre de numéros en double qu'il y a seq. De plus un O (seq.size) les frais généraux

L'avantage de cette solution est qu'une décision négative peut être prise beaucoup plus rapidement (jusqu'à un temps constant), une fois que vous avez payé les frais généraux de construction de la table de recherche.

Pseudocode:

Style impératif:

# 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

Style fonctionnel:

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

Exemple d'implémentation (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 recherche de dictionnaire: codage en tant que machine à états finis

La description

Nous pouvons réduire davantage la complexité algorithmique jusqu'à O (subseq.size) si nous échangeons plus de mémoire. Au lieu de mapper des éléments à leurs indices, nous créons un graphique où chaque nœud représente un élément à son index. Les bords montrent des transitions possibles, par exemple la séquence a, b, aaurait les bords a@1 → b@2, a@1 → a@3, b@2 → a@3. Ce graphique est équivalent à une machine à états finis.

Pendant la recherche, nous maintenons un curseur qui est initialement le premier nœud de l'arbre. Nous marchons ensuite le bord pour chaque élément dans la sous - liste B . Si aucun bord de ce type n'existe, alors B n'est pas une sous-liste. Si après tous les éléments le curseur contient un nœud valide, alors B est une sous-liste.

Pseudocode

Style impératif:

# 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

Style fonctionnel:

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

Exemple d'implémentation (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;

Voici une approche pratique qui évite «le travail acharné» de la mise en œuvre de votre propre algorithme, et évite également de «réinventer la roue»: utilisez un moteur d' expression régulière pour le problème.

Il suffit de mettre tous les nombres de A dans une chaîne et tous les nombres de B dans une chaîne séparés par l'expression régulière (.*). Ajoutez un ^caractère au début et $à la fin. Ensuite, laissez votre moteur d'expression régulière préféré rechercher toutes les correspondances. Par exemple, lorsque

A = (1234356), B = (236)

créer un reg exp pour B comme ^(.*)2(.*)3(.*)6(.*)$. Exécutez maintenant une recherche d'expression rationnelle globale. Pour savoir à quelles positions dans A votre sous-séquence correspond, vérifiez simplement la longueur des 3 premiers sous-matchs.

Si votre plage d'entiers laisse de 0 à 9, vous pouvez envisager de les coder d'abord par des lettres simples pour que cela fonctionne, ou vous devez adapter l'idée à l'aide d'un caractère de séparation.

Bien sûr, la vitesse de cette approche dépendra beaucoup de la vitesse du moteur reg exp que vous utilisez, mais il existe des moteurs hautement optimisés, et je suppose qu'il sera difficile de mettre en œuvre un algorithme plus rapide "prêt à l'emploi" .

Cet algorithme devrait être assez efficace si obtenir la longueur et itérer la séquence est efficace.

1. Comparez la longueur des deux séquences. Conserver plus longtemps sequenceet plus courtsubsequence
2. Commencez au début des deux séquences et bouclez jusqu'à la fin de sequence.
   1. Le nombre à la position actuelle est-il sequenceégal au nombre à la position actuelle desubsequence
   2. Si oui, déplacez encore les deux positions
   3. Sinon, déplacez seulement la position d' sequenceun autre
3. La position est-elle subsequenceà la fin de lasequence
4. Si oui, les deux séquences correspondent
5. Sinon, les deux séquences ne correspondent pas