Existe-t-il des algorithmes permettant de classer un tableau parmi certains modèles ?

Question

Pour un problème simple avec un tableau de longueur 5 pour commencer (en pratique, la longueur du tableau pourrait être de 20 ).

J'ai un prédéfini ensemble de motifs, comme AAAAB, AAABA, BAABC, BCAAA, ... . Chaque motif est de la même longueur que le tableau d'entrée. . J'ai besoin d'une fonction qui prenne n'importe quel tableau d'entiers en entrée et qui renvoie tous les modèles qu'il correspond. ( un tableau peut correspondre à quelques modèles ) aussi vite que possible.

" A "signifie que dans le modèle, tous les nombres situés aux positions de A sont égaux. Par exemple AAAAA signifie simplement que tous les nombres sont égaux, {1, 1, 1, 1, 1} correspond à AAAAA .

" B "signifie que le nombre à la position B n'est pas égal au nombre à la position A. (c'est-à-dire un joker pour un nombre qui n'est pas A). Les nombres représentés par B ne sont pas nécessairement égaux. . Par exemple ABBAA signifie que les 1er, 4e et 5e chiffres sont égaux à, disons x, et que les 2e et 3e chiffres ne sont pas égaux à x. {2, 3, 4, 2, 2} correspond à ABBAA .

" C "signifie que cette position peut être n'importe quel nombre (c'est-à-dire un joker pour un nombre). {1, 2, 3, 5, 1} correspond à ACBBA , {1, 1, 3, 5, 1} correspond également à ACBBA

Je cherche un algorithme efficace (en termes de nombre de comparaisons). Il n'a pas besoin d'être optimal, mais ne devrait pas être trop éloigné de l'optimal. J'ai l'impression que c'est un peu comme l'arbre de décision...

Une méthode très simple mais inefficace est la suivante :

• Essayez de faire correspondre chaque modèle avec l'entrée. say AABCA contre {a, b, c, d, e} . Il vérifie si (a=b=e && a!=c) .

• Si le nombre de motifs est n la longueur du motif/réseau est de m alors la complexité est d'environ O(n*m)

Mise à jour :

N'hésitez pas à suggérer de meilleures formulations pour la question. Je ne sais pas comment faire pour que la question soit simple à comprendre et ne prête pas à confusion.

Un algorithme idéal nécessiterait une sorte de préparation, par exemple pour transformer l'ensemble des modèles en un arbre de décision. De sorte que les complexités après le prétraitement peut être atteint à quelque chose comme O(log n * log m) pour certains ensembles de modèles spéciaux (juste une supposition).

Quelques chiffres qui peuvent être utiles : les ensembles de modèles prédéfinis sont approximativement de la taille de 30. Le nombre de tableaux d'entrée à comparer est d'environ 10 millions.

Dis, si AAAAA y AAAAC sont tous deux dans le jeu de modèles prédéfinis. Alors si AAAAA matches, AAAAC également. Je cherche un algorithme qui pourrait reconnaître cela.

Mise à jour 2

La réponse de @Gareth Rees donne une solution O(n), mais en supposant qu'il n'y a pas beaucoup de " C "s. (sinon le stockage est énorme et les comparaisons inutiles nombreuses)

J'apprécierais également toute idée sur la manière de gérer les situations où il y a beaucoup de " C "s, disons, pour un tableau d'entrée de longueur 20, il y a au moins 10 " C " pour chaque modèle prédéfini.

Answer 1

Voici une idée qui permet d'échanger O(2 n ) la préparation et le stockage de O( n )-ish runtime. Si vos tableaux ne sont pas plus longs que la taille des mots de votre machine (vous laissez entendre que 20 serait une taille typique), ou s'il n'y a pas trop d'occurrences de C dans les modèles, cette idée pourrait vous convenir. (Si aucune de ces conditions n'est remplie, évitez !)

1. (Étape préparatoire, faite une fois) Créer un dictionnaire d la mise en correspondance des nombres avec des ensembles de modèles. Pour chaque motif p et chaque sous-ensemble S des occurrences de C dans ce modèle, laissez n est le nombre qui a un bit activé correspondant à chaque A dans le motif, et pour chaque occurrence de C sur S . Ajouter p à l'ensemble des motifs d [ n ].

2. (Les étapes restantes sont effectuées chaque fois qu'un nouveau tableau doit être comparé aux modèles). Créez un dictionnaire e la mise en correspondance des chiffres avec les chiffres.

3. Soit j parcourir les indices du tableau, et pour chaque j :

   1. Soit i être le j -ème entier dans le tableau.

   2. Si i n'est pas dans le dictionnaire e ensemble e [ i ] = 0.

   3. Définir e [ i ] = e [ i ] + 2 j 1 où est la longueur du tableau.

4. Maintenant, les clés de e sont les nombres distincts i dans le tableau, et la valeur e [ i ] a un bit activé correspondant à chaque occurrence de i dans le tableau. Pour chaque valeur e [ i ] qui se trouve dans le dictionnaire d tous les motifs de l'ensemble d [ e [ i ]] correspondent au tableau.

(Note : en pratique, vous construisez les ensembles de bits dans l'autre sens, et utilisez 2 j à l'étape 3.3 au lieu de 2 j 1 mais j'ai décrit l'algorithme de cette façon pour la clarté de l'exposé).

Voici un exemple. Supposons que nous ayons les motifs AABBA y ACBBA . Dans l'étape de prétraitement AABBA se transforme en le nombre 25 (11001 en binaire), et ACBBA se transforme en les nombres 25 (11001 en binaire) et 17 (10001 en binaire), pour les deux sous-ensembles possibles des occurrences de C dans le motif. Ainsi, le dictionnaire d ressemble à ça :

• 17 { ACBBA }
• 25 { AABBA , ACBBA }

Après avoir traité le tableau {1, 2, 3, 5, 1}, nous avons e \= {1 17, 2 8, 3 4, 5 2}. La valeur e [1] = 17 se trouve dans d donc cette entrée correspond au modèle ACBBA .

Après avoir traité le tableau {1, 1, 2, 3, 1}, nous avons e \= {1 25, 2 4, 3 2}. La valeur e [1] = 25 se trouve dans d donc cette entrée correspond aux modèles AABBA y ACBBA .

Answer 2

Obtenez l'index du premier A dans le motif, obtenir la valeur pour cette position, puis parcourir les positions en boucle.

Pour vérifier si le tableau array correspond au motif de la chaîne de caractères pattern le résultat est dans le booléen match :

int index = pattern.IndexOf('A');
int value = array[index];
bool match = true;
for (int i = 0; i < array.Length; i++) {
  if (pattern[i] != 'C' && i != index) {
    if ((pattern[i] == 'A') != (array[i] == value)) {
      match = false;
      break;
    }
  }
}