debruijn sequenzen generieren



  • hallo,
    ich wuesste gerne ob jemand von euch ad-hoc einen algorithmus (pseudo-code) wuesste wie man eine debruijn sequenz der laenge n erzeugen kann (muss nicht die eleganteste weise sein)!?!?

    eine debruijn sequenz der laenge n ist ein bitwort der laenge n wobei jede untersequenz der laenge lg(n) nur einmal im ganzen bitwort vertreten ist (man beachte, dass eine untersequenz auch ueber anfang und ende eines bitworts erstrecken kann).

    z.B.: das bitwort (in hex) 0x077CB531 ist eine debruijn sequenz der laenge 32 (32 bits) wobei jede untersequenz der laenge lg(32) -> also der laenge 5, nur einmal in dem gesamten bitwort vorkommt.

    danke vorab.


Log in to reply