de Bruijn arbitrary sequences

This program calculates the de Bruijn sequence and code for arbitrary length (or number of objects coded). In principle, it can use bases from 2 .. 62 (digits represented as 0..9A..Za..z) which can be seen as the number of "states" for an object. Default base of 2 (2 states: 0 and 1)). But for performance reasons, only base 2..4 is allowed and the range of sequence lengths is from 2..64. Sorry, about that. This constraint may be removed in the future.

There are two "types" of representation. The normal representation shows the base-ary representation in normal way (7 as "0111") and the cycle starts with the lowest number. The reverse type reverses the base-ary presentation (7 is "1110") and the cycle starts with the highest number.

Please note that this version uses a randomized approach for calculating a cycle of proper length, so it may take some seconds for large number of objects. This also means that the result may differ for different runs of the same numbers of objects and base.

The normal definitions of a de Bruijn sequence use another approach for calculating the codes. See more about these de Bruijn sequences at my page de Bruijn sequence page (as Java Applet), which also has some references.

This program was presented in the (swedish) blog post de Bruijn-sekvenser av godtycklig längd and may contain some more pointers. It was also mentioned in the blog post de Bruijn sequences in Gecode (and other systems).

N (2..64):
Base (2..4):
Type: normal reversed
Show connections: yes no
Show sequence check: yes no
Show sequence statistics: yes no

Result

Sequence: 0000101100111101
Sequence statistics (number of each type): Cycle (in decimal): 0 1 2 5 11 6 12 9 3 7 15 14 13 10 4 8

Connections
0: 0->0 0->1
1: 1->2 1->3
2: 2->4 2->5
3: 3->6 3->7
4: 4->8 4->9
5: 5->10 5->11
6: 6->12 6->13
7: 7->14 7->15
8: 8->0 8->1
9: 9->2 9->3
10: 10->4 10->5
11: 11->6 11->7
12: 12->8 12->9
13: 13->10 13->11
14: 14->12 14->13
15: 15->14 15->15

Sequence check
0000101100111101000
0000 (0)
 0001 (1)
  0010 (2)
   0101 (5)
    1011 (11)
0000101100111101000
     0110 (6)
      1100 (12)
       1001 (9)
        0011 (3)
         0111 (7)
0000101100111101000
          1111 (15)
           1110 (14)
            1101 (13)
             1010 (10) (wrapped)
              0100 (4) (wrapped)
0000101100111101000
               1000 (8) (wrapped)

See also:
* "ordinary" de Bruijn sequences (as Java Applet)
* debruijn_binary.mzn, a model in MiniZinc constraint programming language.
* DeBruijn.java, a model in JaCoP constraint programming language (Java)
* DeBruijn.java, a model in Choco constraint programming language (Java)
* debruijn_binary.rb, a model in Gecode/R constraint programming language (Ruby interface to Gecode)
* debruijn.co, a model in Comet another constraint programming language
* debruijn.cpp, a model in Gecode a constraint programming language in C++


These models were discussed in the blog post de Bruijn sequences in Gecode (and other systems).

Back to my homepage
Created by Hakan Kjellerstrand hakank@bonetmail.com