Regelmäßigkeit in einer Bitfolge

12.10.2009, 01:01	gitterrost4	Auf diesen Beitrag antworten »
Regelmäßigkeit in einer Bitfolge Hallo, Ich habe vor kurzem ein Programm erstellt, welches mir eine Bitfolge ausgibt, die alle möglichen Bitfolgen der Länge $\begin{eqnarray} n \end{eqnarray}$ enthält. Die erste Idee, die natürlich Korrekt ist, ist alle möglichen Bitfolgen einfach aneinanderzureihen. Hierbei treten jedoch viele Bitfolgen doppelt auf. Die Folgenlänge liegt in $\begin{eqnarray} O(n\cdot2^n) \end{eqnarray}$ . Dann bin ich auf einen Algorithmus gekommen, der mir eine Bitfolge der Länge $\begin{eqnarray} 2^n+n-1 \in O(2^n) \end{eqnarray}$ ausgibt. Den Beweis, dass der Algorithmus korrekt arbeitet und dass es die kürzestmögliche Bitfolge ist, habe ich schon geführt. Das Prinzip ist folgendes: 1. Schreibe eine Liste der möglichen Bitfolgen (00000..00 bis 11111...11). 2. Beginne die Bitfolge mit $\begin{eqnarray} n \end{eqnarray}$ -mal der 0 und Streiche die 0000..00 aus der Liste 3. Nimm die letzten $\begin{eqnarray} n-1 \end{eqnarray}$ Bits der schon geschriebenen Folge 3.1 Wenn diese Bits mit einer 1 angehängt noch in der Liste ist, dann schreib eine 1 und lösch die entsprechende Zahl aus der Liste 3.2 Sonst häng eine 0 an und lösch die entsprechende Zahl aus der Liste. 4. Wiederhole 3. bis die Liste leer ist. Diesen Algorithmus habe ich nun versucht in C++ umzusetzen. Soweit arbeitet es auch korrekt, jedoch bekomme ich ab $\begin{eqnarray} n=23 \end{eqnarray}$ einen Segfault, was vermutlich daran liegt, dass er ein Array mit $\begin{eqnarray} 2^{23} \end{eqnarray}$ Elementen abspeichern muss. Nun die Frage: Lässt sich in der entstehenden Bitfolge eine Regelmäßigkeit finden, sodass ich aus den letzten $\begin{eqnarray} k \end{eqnarray}$ Bits (oder etwas ähnliches) das nächste Bit berechnen kann? Ein paar Bitfolgen sind: n=2: 00110 n=3: 0001110100 n=4: 0000111101100101000 n=5: 000001111101110011010110001010010000 n=6: 000000111111011110011101011100011011010011001011000010101000100100000 Am besten wäre irgendetwas, sodass ich die Folge Zeichen für Zeichen ausgeben kann für ein beliebiges $\begin{eqnarray} n \end{eqnarray}$ (natürlich bis MAXINT) Danke schonmal. MfG gitterrost4 EDIT: recht wäre mir auch ein Algorithmus, der einen anderen String gleicher Länge ausgibt (dann auch Bit für Bit).
13.10.2009, 23:50	outSchool	Auf diesen Beitrag antworten »
RE: Regelmäßigkeit in einer Bitfolge Hallo, ich habe mir mal die Zeichenfolge vertikal dargestellt. Hier zur besseren Übersicht nur ein Auschnitt für n = 4. $\begin{eqnarray} \begin{vmatrix} & & & & & & 0 \\ & & & & & & 0 \\ & & & & & & 0 \\ & 1 & \| & 0 & 0 & 0 & 0 \\ & 2 & \| & 0 & 0 & 0 & 1 \\ & 3 & \| & 0 & 0 & 1 & 1 \\ & 4 & \| & 0 & 1 & 1 & 1 \\ & 5 & \| & 1 & 1 & 1 & 1 \\ & 6 & \| & 1 & 1 & 1 & 0 \\ & 7 & \| & 1 & 1 & 0 & 1 \\ & 8 & \| & 1 & 0 & 1 & 1 \\ & 9 & \| & 0 & 1 & 1 & 0 \\ & 10 & \| & 1 & 1 & 0 & \\ & 11 & \| & 1 & 0 & & \\ & 12 & \| & 0 & & & \end{vmatrix} \end{eqnarray}$ Die Bitfolge ist also ganz rechts. Mit der vierten Null kann die Zeile 1 gestrichen werden. Dann kommt 4-mal die 1. In Zeile 6 kommt dann ganz rechts eine Null, eine 1 ist nicht möglich wegen Zeile 5. Nun folgen ganz rechts solange 1-en bis ganz links die 0 steht (Zeile 9). In Zeile 10 kommt rechts eine 0, weil die 1-er mit einer 0 zuvor schon abgearbeitet wurden. Zu der (letzten) Nulldiagonale kommt eine weitere Nulldiagonale hinzu. Dies kannst du entsprechend weiter ausbauen. Sieht man sich deine Bitfolgen für n = 2 bis 6 an so fällt folgendes auf: n=2: 00110 n=3: 0001110100 n=4: 0000111101100101000 n=5: 000001111101110011010110001010010000 n=6: 000000111111011110011101011100011011010011001011000010101000100100000 Für die Folge von n Bits (nBits genannt): 1. n-mal die 0 2. n-mal die 1 3. 1-mal die 0 (sonst wäre 11...1 doppelt) 4. (n-2)-mal die 1 (das sind die n-Bits, die am Anfang und Ende eine 1 haben und in der Mitte eine 0, die von rechts nach links wandert) 5. 2-mal die 0 (das ist der Sprung zu den nBits, die 2 Nullen haben) 6. (n-3)-mal die 1 (siehe 4. nur in der Mitte 2-mal 0 nebeneinander) Für n = 4 kommt jetzt schon die Abschlussbedingung. Die viertletzte Ziffer ist 1 die letzten 3 Ziffern sind 0. Das letzte nBit ist also 10...0, d.h., die nBits werden fortlaufend mit einer 0 angereichert. Von Vorteil ist, wenn die Anzahl der Nullen und Einsen mitgezählt wird. Das ist schon mal der erste Entwurf, für n > 4 muss ich nochmal sehen ob meine Idee allgemeingültig ist.
14.10.2009, 00:04	gitterrost4	Auf diesen Beitrag antworten »
Und hier fängt es an für mich (zumindest scheinbar) unregelmäßig zu werden: 7. Es folgt unabhängig von n: 010 Gruß Paul
20.02.2010, 18:42	gitterrost4	Auf diesen Beitrag antworten »
Ich weiß es ist schon etwas her... ich hatte im Semester nicht wirklich Zeit mich damit zu beschäfitgen. Einige neue Erkenntnisse habe ich gewonnen. Ich habe mich ein wenig von meinem Algorithmus entfernt und mal geschaut, wieviele verschiedene Strings kürzester Länge gibt, die den Anforderungen entsprechen. Bei n=1 ist das 01 und 10; also 2 verschiedene. Bei n=2 gibt es 00110, 11001, 01100 und 10011; also 4 verschiedene. Bei n=3 gibt es 16 verschiedene. Bei n=4 gibt es 256 verschiedene. (Diese Werte sind zu 99% richtig. Ich hab sie durch Bruteforce (also alle Möglichkeiten aufschreiben und die, die nicht gehen, rausschmeißen) bestimmt. Bei n=5 ist allerdings die anzahl an verschiedenen Möglichkeiten zu groß ( $\begin{eqnarray} 2^{36} \end{eqnarray}$ ). Jedenfalls sieht es aus, als ob die Anzahl der gültigen Bitfolgen kürzester Länge für n beschrieben wird durch $\begin{eqnarray} 2^{2^{n-1}} \end{eqnarray}$ Eine Stichprobe von vier Zahlen ist zwar nicht aussagekräftig, aber es sieht doch sehr stark danach aus. Das Problem vereinfacht sich also dazu, aus diesen Bitfolgen eine zu finden, die sich Algorithmisch einfach bestimmen lässt. Jede Idee wird gern angenommen! EDIT: Hier Links zu Dateien, wo die gültigen Bitfolgen aufgelistet sind: n=3 n=4

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »