Enumerazione di tutte le stringhe che soddisfano determinate restrizioni

Question

Sto cercando il nome della seguente classe di problemi, in modo da poter cercare su Google algoritmi efficaci e maggiori informazioni.

Ho un alfabeto con tre caratteri {-1, 0, 1}.

Devo generare in modo efficace tutte le stringhe di lunghezza 24 che sono principalmente {0} ma hanno da zero a otto {1, -1} caratteri distribuiti in determinati schemi. (I modelli comportano restrizioni sul numero e sugli accoppiamenti di {-1}). Le stringhe di numeri totali che soddisfano i miei criteri sono piuttosto modeste: circa 128.000.

Qual è il nome di questa classe di problema / algoritmo?

Answer 1

Non sono sicuro che esista una classe di algoritmi "ben definita" per questo questo; è solo un esercizio di combinatoria. Puoi eseguire la generazione in tre passaggi:

1. Genera tutti i numeri a 24 bit con 8 o meno bit impostati (potresti essere in grado di accelerare un po 'se precompili alcune tabelle di ricerca)
2. Per ogni numero a 24 bit con n bit impostati, scorrere su tutti i numeri n-bit
3. Se il kth bit del numero n-bit è 0, il kth bit impostato del numero a 24 bit viene stampato come -1, altrimenti viene stampato come 1

Per spiegare meglio i passaggi 2-3, dire che il numero a 24 bit ha 4 bit impostati e assomiglia a

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

Quindi, ripetiamo tutti i 16 numeri a 4 bit da 0 0 0 0 a 1 1 1 1 e, ad esempio:

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

Se hai bisogno di risolverlo solo una volta, forse potresti semplicemente forzarlo e inserire i risultati in una tabella di ricerca nella tua applicazione. Ci sono meno di trilioni di sequenze da 24 bit di 0,1, -1 da controllare.

Se forse sto sbagliando la mia matematica o hai bisogno di risolvere dinamicamente il problema in fase di esecuzione, considererei il problema come un sistema di 24 variabili ognuna limitata a -1, 0, 1 e approcciarlo come < a href = "http://it.wikipedia.org/wiki/Constraint_satisfaction_problem" rel = "nofollow noreferrer"> Problema di soddisfazione dei vincoli , supponendo che tu possa enumerare i tuoi vincoli in qualche modo. La mia preoccupazione, tuttavia, è che, dal momento che è necessario vedere tutte soluzioni e non solo un sottoinsieme, è possibile rimanere bloccati in modo esaustivo nella ricerca dello spazio del problema.

Questo documento sembra proprio nel tuo vicolo: Elenco di tutte le soluzioni per problemi di soddisfazione dei vincoli . Anche se non ho accesso al testo completo del documento per vedere se aiuta.

Potrei abbaiare insieme l'albero sbagliato, ma forse questo è un punto di partenza

Answer 3

Una mia risposta completamente separata dal mio ultimo, poiché il codice di lavoro tende a superare i collegamenti ai documenti di ricerca, ho trovato questo codice su Forum di fisica e non posso prendermi il merito da solo, l'ho appena risolto in modo che sia stato compilato sotto g ++ e modificato in costanti per cercare 8 bit in 24. Elenca molto rapidamente tutti i 24 stringhe di bit con 8 bit attivi e ce ne sono solo circa 735.000. Questi "modelli" mostrano gli unici schemi validi per i tuoi personaggi diversi da zero. Dovresti quindi prendere ognuna di queste 735.000 risposte e lanciare i segni - / + e decidere se ognuna soddisfa i tuoi criteri, ma in questo modo stai iniziando da 735k possibili soluzioni invece di 200 miliardi.

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