Enumerar todas las cadenas que cumplan las restricciones dadas

Question

Estoy buscando el nombre de la siguiente clase de problema, para poder buscar en Google algoritmos efectivos y más información.

Tengo un alfabeto con tres caracteres {-1, 0, 1}.

Necesito generar efectivamente todas las cadenas de longitud 24 que son en su mayoría {0} pero tienen de cero a ocho {1, -1} caracteres distribuidos en ciertos patrones. (Los patrones implican restricciones en el número y emparejamientos de {-1}). Las cadenas de números totales que cumplen con mis criterios son bastante modestas: alrededor de 128,000.

Entonces, ¿cuál es el nombre de esta clase de problema / algoritmo?

Answer 1

No estoy seguro de que haya una "clase de algoritmo" bien definida por esto esto; Es solo un ejercicio de combinatoria. Puede hacer la generación en tres pasos:

1. Genere todos los números de 24 bits con 8 o menos bits configurados (puede acelerar esto un poco si calcula previamente algunas tablas de búsqueda)
2. Para cada número de 24 bits con n bits establecidos, repita todos los números de n bits
3. Si el késimo bit del número de n bits es 0, entonces el kth set bit del número de 24 bits se imprime como -1, de lo contrario se imprime como 1

Para explicar los pasos 2-3 un poco mejor, digamos que su número de 24 bits tiene 4 bits establecidos y parece

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

Luego, iteramos sobre los 16 números de 4 bits de 0 0 0 0 a 1 1 1 1 y, por ejemplo:

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 solo necesita resolver esto una vez, tal vez podría simplemente forzarlo y poner los resultados en una tabla de búsqueda en su aplicación. Hay menos de un billón de secuencias de 24 bits de 0,1, -1 para verificar.

Si tal vez estoy haciendo mis cálculos incorrectos o necesita resolver dinámicamente el problema en tiempo de ejecución, consideraría el problema como un sistema de 24 variables cada una limitada a -1, 0, 1 y lo abordaría como un < a href = "http://en.wikipedia.org/wiki/Constraint_satisfaction_problem" rel = "nofollow noreferrer"> Problema de satisfacción de restricciones , suponiendo que puede enumerar sus restricciones de alguna manera. Sin embargo, mi preocupación es que, dado que necesita ver las soluciones todas y no solo un subconjunto, aún puede estar atrapado buscando exhaustivamente el espacio del problema.

Este artículo parece adecuado para usted: Enumeración de todas las soluciones para problemas de satisfacción de restricciones . Aunque no tengo acceso al texto completo del documento para ver si ayuda.

Puedo estar ladrando el árbol equivocado todos juntos, pero tal vez este es un punto de partida

Answer 3

Una respuesta completamente separada de la última, ya que el código de trabajo tiende a superar los enlaces a los trabajos de investigación, encontré este código en Foro de Física y no puedo darme el mérito, lo arreglé para que se compilara en g ++ y cambié a constantes para buscar 8 bits en 24. Enumera muy rápidamente los 24 cadenas de bits con 8 bits, y solo hay unos 735,000 de estos. Estas 'plantillas' muestran los únicos patrones válidos para sus caracteres distintos de cero. Luego, tendría que tomar cada una de estas 735,000 respuestas y colocar los signos - / + y decidir si cada uno cumple con sus criterios, pero de esta manera está comenzando con 735k posibles soluciones en lugar de 200 mil millones.

#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;
  }
 }