Énumération de toutes les chaînes rencontrant des restrictions

Question

Je cherche le nom de la classe de problèmes suivante afin de pouvoir rechercher des algorithmes efficaces et plus d'informations sur Google.

J'ai un alphabet avec trois caractères {-1, 0, 1}.

Je dois générer efficacement toutes les chaînes de longueur 24 qui sont pour la plupart {0} mais qui ont zéro à huit {1, -1} caractères répartis dans certains modèles. (Les modèles impliquent des restrictions sur le nombre et les paires de {-1}). Le nombre total de chaînes correspondant à mes critères est assez modeste: environ 128 000.

Alors, quel est le nom de cette classe de problèmes / algorithmes?

Answer 1

Je ne suis pas sûr qu'il existe une "classe d'algorithmes" bien définie. pour cela ceci; c'est juste un exercice de combinatoire. Vous pouvez faire la génération en trois étapes:

1. Générez tous les nombres de 24 bits avec 8 bits ou moins (vous pourrez peut-être accélérer un peu si vous précalculez certaines tables de recherche)
2. Pour chaque nombre de 24 bits avec n bits défini, effectuez une itération sur tous les nombres de n bits
3. Si le k-bit du nombre de n-bits est 0, alors le k-bit défini du nombre de 24 bits s'imprime en tant que -1, sinon il apparaît en tant que 1

Pour expliquer les étapes 2-3 un peu mieux, dites que votre numéro à 24 bits a 4 bits définis et ressemble à

0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0

Ensuite, nous parcourons les 16 nombres de 4 bits de 0 0 0 0 à 1 1 1 1 , et par exemple:

0 0 0 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 -1 0 0 0 0
0 1 1 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0  1  1 0 0 0 0 0 -1 0 0 0 0
0 1 0 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0  1 -1 0 0 0 0 0 -1 0 0 0 0
1 1 1 1 gives the string  0 0 0  1 0 0 0 0 0 0 0 0  1  1 0 0 0 0 0  1 0 0 0 0

Answer 2

Si vous ne devez résoudre ce problème qu'une seule fois, vous pouvez peut-être simplement le forcer brutalement et placer les résultats dans un tableau de recherche dans votre application. Il y a moins d'un billion de séquences 24 bits de 0,1, -1 à vérifier.

Si je fais peut-être mal mes calculs ou si vous devez résoudre le problème de manière dynamique au moment de l'exécution, je considérerais le problème comme un système de 24 variables, chacune limitée à -1, 0, 1 et l'abordant comme < a href = "http://en.wikipedia.org/wiki/Constraint_satisfaction_problem" rel = "nofollow noreferrer"> Problème de satisfaction des contraintes , en supposant que vous puissiez énumérer vos contraintes d'une manière ou d'une autre. Ce qui me préoccupe cependant, c'est que puisque vous avez besoin de voir toutes toutes les solutions et pas seulement un sous-ensemble, vous êtes peut-être toujours en train de chercher de manière exhaustive dans l'espace du problème.

Ce document semble vous plaire: Énumérer toutes les solutions aux problèmes de satisfaction des contraintes . Bien que je n’ai pas accès au texte intégral du document pour savoir s’il est utile.

Je suis peut-être en train d'aboyer le mauvais arbre tous ensemble, mais c'est peut-être un point de départ

Answer 3

Réponse tout à fait distincte de ma dernière question, le code de travail ayant tendance à l'emporter sur les liens des documents de recherche, j'ai trouvé ce code à l'adresse Physics Forum et ne peut en prendre le crédit moi-même, je viens de le réparer, il a donc été compilé sous g ++ et modifié en constantes pour rechercher 8 bits sur 24. Il énumère très rapidement les 24 chaînes de bits avec 8 bits, et il n'y en a que 735 000 environ. Ces "modèles" affichent les seuls modèles valides pour vos caractères non nuls. Il vous faudrait ensuite examiner chacune de ces 735 000 réponses et jeter les signes - / + et décider si chacune répond à vos critères, mais de cette façon, vous partez de 735 000 solutions possibles au lieu de 200 milliards.

#include <stdio.h>

 int main()
 {
 int size = 24;
 int pop = 8;

 int n = ((1 << pop) - 1) << (size - pop);

 while(true) {
    printf( "%x\n",n);

    int lowest = n & -n;

     if(lowest > 1) {
        n = n ^ lowest ^ (lowest >> 1);
        continue;
     }

     int high = n & (n + lowest);
     if(high == 0) break;

     int low = n ^ high;

     low = (low << 2) + 3;

     while((low & high) == 0) low <<= 1;
     n = high ^ low;
  }
 }