Verfahren gesucht

[mike (Gast)]

Hallo,

ich hatte mal vor 2 Jahren ein Verfahren gefunden, mit dem folgendes 
möglich war.

Sagen wir, wir haben eine 4bit Zahl. Diese kann also die Gestalt von 
0000 bis 1111 annehmen.
Nun gibt es die Möglichkeit, eine Zahl zu generieren (mit einigen mehr 
Bits), die alle 2^4 möglichen Zahlen enthält, aber nur eine minimale 
Größe hat.
Wie heißt dieses Verfahren, bzw wie generiert man diese Zahl?

Danke

[Mol (Gast)]

Find erst mal ein Verfahren um deine Frage klar zu formulieren.

[Tom M. (tomm)]

mike schrieb:
> Nun gibt es die Möglichkeit, eine Zahl zu generieren (mit einigen mehr
> Bits), die alle 2^4 möglichen Zahlen enthält, aber nur eine minimale
> Größe hat.

Du meinst eine möglichst kurze Bitfolge, in der sämtliche 4-bit-Folgen 
von 0000..1111 enthalten sind? Überlappend erlaubt oder nicht?

[AVerr (Gast)]

So wie ich das verstanden habe, sucht der TO ein Verfahren, um alle 
möglichen Bitkombinationen in einer Zahl zu bekommen, die so kurz wie 
möglich ist.

Beispiel mit 2 Bit:
4 mögliche Bitkombinationen - 00, 01, 10, 11

Eine mögliche Lösung wäre 00011011, darin kommen alle 4 Bitkombinationen 
vor. Jedoch ist das nicht die kürzeste Lösung.

00110 ist besser:
00 110
0 01 10
00 11 0
001 10

[AVerr (Gast)]

Tom M. schrieb:
> Überlappend erlaubt oder nicht?

Ich gehe von Überlappend aus, sonst wäre es unsinnig, die kürzeste Zahl 
mit diesen Eigenschaften zu suchen.
Nicht-überlappende Zahlen wären dann alle (mindestens) 64 Bit ( = 16 
Kombinationen á 4 Bit ) lang.

[mike (Gast)]

Hallo,

ganz genau, es geht um Überlappung.

Ich bin mir sicher, dass diese Verfahren einen Namen hat. Aber wichtiger 
ist mir, wie ich solch eine Zahl Synthetisieren kann.

Danke

[flof (Gast)]

Ich vermute, das gesuchte ist eine de Brujin Sequenz,
eng verwandt mit dem de Brujin Graphen:
http://en.wikipedia.org/wiki/De_Bruijn_graph

[mike (Gast)]

Hallo,

float, genau das habe ich gesucht, danke dir vielmals! ;)

[Jobst M. (jobstens-de)]

Ich dachte ja nun an sowas:

0000100110101111000

0000
 0001
  0010
   0100
    1001
     0011
      0110
       1101
        1010
         0101
          1011
           0111
            1111
             1110
              1100
               1000


Gruß

Jobst

[mike (Gast)]

Hi,

das ist die de Bruijn Sequenz


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

und das ist deine

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

exact das gleiche, nur dass man die letzten drei Nullen bei dir 
Streichen kann, denn wenn man wieder von vorne beginnt, hat man schon 4 
nullen.

Gruß

[Jobst M. (jobstens-de)]

Und wo ist die Kombination 1000 in Deiner Sequenz?
Und 1100 ?
Und 1110 ?


Edit: Ach, das Ding soll sich im Kreis drehen?


Gruß

Jobst