Aufzählen alle Strings Treffen gegeben Einschränkungen

Question

Ich bin für den Namen der folgenden Klasse des Problems suchen, so dass ich für eine effektiven Algorithmen und weitere Informationen googeln kann.

Ich habe ein Alphabet mit drei Zeichen {-1, 0, 1}.

Ich muss effektiv alle Strings der Länge 24, die meist sind erzeugen {0} aber haben null bis acht {1, -1} Zeichen in bestimmten Mustern verteilt. (Die Muster beinhalten Beschränkungen für die Anzahl und Paarungen von {-1}). Die Gesamtzahl Strings, die meine Kriterien erfüllen, sind recht bescheiden.: Über 128.000

Also, was ist der Name für diese Klasse von Problem / Algorithmus?

Answer 1

Ich bin mir nicht sicher, dass es eine gut definierte „Algorithmus-Klasse“ für diese diese; es ist nur eine Übung in der Kombinatorik. Sie können in drei Schritten die Erzeugung tun:

1. generieren alle 24-Bit-Zahlen mit 8 oder weniger Bits (Sie können, kann dies ein wenig beschleunigen, wenn Sie einige Lookup-Tabellen precompute)
2. Für jede 24-Bit-Zahl mit n Bits, iterieren alle n-Bit-Zahlen
3. Wenn der k-te Bit der n-Bit-Zahl 0, dann der k-te gesetzt Bit der 24-Bit-Zahl druckt als -1, sonst ist es druckt als 1

Schritte Um zu erklären, 2-3 ein bisschen besser sagen, dass Ihre 24-Bit-Zahl 4 Bits gesetzt und sieht aus wie

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

Dann iterieren wir über alle 16 4-Bit-Zahlen von 0 0 0 0 zu 1 1 1 1, und, zum Beispiel:

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

Wenn Sie nur diese müssen einmal lösen, vielleicht konnte man nur Brute es Kraft und setzt die Ergebnisse in einer Lookup-Tabelle in Ihrer Anwendung. Es gibt weniger als eine Billion 24-Bit-Sequenzen von 0,1, -1 zu überprüfen.

Wenn vielleicht mache ich meine Mathe falsch oder Sie brauchen, um dynamisch das Problem zur Laufzeit zu lösen, würde ich das Problem als ein System von 24 Variablen jeweils begrenzt auf -1, 0, 1 und nähere wir ihn als eine betrachten < a href = "http://en.wikipedia.org/wiki/Constraint_satisfaction_problem" rel = "nofollow noreferrer"> Constraint Satisfaction Problem , vorausgesetzt, Sie Ihre Einschränkungen in irgendeiner Weise aufzählen kann. Meine Sorge ist jedoch, dass, da Sie benötigen Sehen alle Lösungen und nicht nur eine Teilmenge, Sie noch erschöpfend aufgeklebt werden kann das Problem Raum zu suchen.

Dieses Papier scheint bis Ihre Gasse: Alle Lösungen Aufzählen für Constraint Satisfaction Probleme . Obwohl ich keinen Zugriff auf den vollständigen Wortlaut des Papiers zu sehen, ob es hilft.

Ich kann den falschen Baum alle zusammen bellen, aber vielleicht ist dies ein Ausgangspunkt

Answer 3

Eine völlig separate Antwort von meinem letzten, als Code zu arbeiten Trumpf Links neigt Papiere zu erforschen, fand ich diesen Code in Physik Forum und kann nicht für es selbst nehmen Kredit, ich kann es nur so fixiert, um es unter g ++ kompiliert und geändert, um Konstanten für 8 Bits in 24 zu sehen es ist sehr schnell alle 24 aufzählt Bit-Ketten mit 8 Bit auf, und es gibt nur etwa 735.000 davon. Diese ‚Vorlagen‘ zeigen das einzig gültige Muster für Ihre Nicht-Null-Zeichen. Sie würden dann jedes dieser 735.000 Antworten nehmen müssen und werfen um die -. / + Zeichen und entscheiden, ob jedes Sie Kriterien erfüllt, aber auf diese Weise Sie starten bei 735k mögliche Lösungen anstelle von 200 Milliarden

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