Project K.12: de Bruijn sequences
A de Bruijn sequence of order $n$ is a sequence of $2^n$ 0s and 1s such that every possible sequence of $n$ bits appears exactly once.
For example, an de Bruijn sequence of order 3 is
00010111
When this is cycled,
0001011100010111
you will observe that the sequence contains:
000 0
001 1
010 2
101 5
011 3
111 7
110 6
100 4
Because every triplet of 0s and 1s appears exactly once, it is now possible to tell where you are simply based on reading off any sequence of three bits.
Now, there are $2^{2^{n - 1} - n}$ different de Bruijn sequences of order $n$. We will describe a technique for generating one of those sequences here.
We will define a right rotation of an $n$-bit number as a shift of the $n$ bits to the right where the least-significant bit (the one most to the right) is moved into the most significant position of the $n$ bits.
For example, six successive right rotation of these six bits are shown here:
0000000000011010 0000000000001101 0000000000100110 0000000000010011 0000000000101001 0000000000110100 0000000000011010
You will note that after six right rotations, the the $6$-bit number reverts back to the original value.
Here is an example where the number reverts back to its original value after only three right rotations:
0000000000001001 0000000000100100 0000000000010010 0000000000001001
To create a de Bruijn sequence of order $n$, begin iterating $k$ from $1$ to $2^n - 1$:
- If any of the $n$ right rotations of $k$ has a numeric value less than $k$, we will discard $k$.
- If we have not discarded $k$, let $m$ be the least number of rotations required to obtain a value equal to $k$. The last $m$ bits of $k$ will form the next $m$ bits of the de Bruijn sequence.
We can make some observations:
- The first bit will always be 0.
- The last bit will always be 1.
Apart from $k = 0$, it should be clear that if the least significant bit of $k$ is not $1$, then that number will will not form a part of the de Bruijn sequence, so we can immediately discard that $k$ from consideration.
Less obvious is that there will be $2^n$ bits altogether.
k smaller contribution
rotation to sequence
0000 0
0001 0001
0010 0001
0011 0011
0100 0001
0101 01
0110 0011
0111 0111
1000 0001
1001 0011
1010 0101
1011 0111
1100 0011
1101 0111
1110 0111
1111 1
Thus, the de Bruijn sequence is 0000100110101111. You will note that we get all possible sequences of four bits from this sequence:
00001001101011110000100110101111 0000 0 0001 1 0010 2 0100 4 1001 9 0011 3 0110 6 1101 13 1010 10 0101 5 1011 11 0111 7 1111 15 1110 14 1100 12 1000 8 0000 0
k smaller contribution
rotation to sequence
00000 0
00001 00001
00010 00001
00011 00011
00100 00001
00101 00101
00110 00011
00111 00111
01000 00001
01001 00101
01010 00101
01011 01011
01100 00011
01101 01011
01110 00111
01111 01111
10000 00001
10001 00011
10010 00101
10011 00011
10100 00101
10101 01101
10110 01011
10111 01111
11000 00011
11001 00111
11010 01101
11011 01111
11100 00111
11101 01111
11110 01111
11111 1
Thus, the de Bruijn sequence is 00000100011001010011101011011111. You will note that we get all possible sequences of five bits from this sequence:
0000010001100101001110101101111100000100011001010011101011011111 00000 0 00001 1 00010 2 00100 4 01000 8 10001 17 00011 3 00110 6 01100 12 11001 25 10010 18 00101 5 01010 10 10100 20 01001 9 10011 19 00111 7 01110 14 11101 29 11010 26 10101 21 01011 11 10110 22 01101 13 11011 27 10111 23 01111 15 11111 31 11110 30 11100 28 11000 24 10000 16 00000 0
Note: We are giving you an algorithm that works, but we are not justifying it. If you wish to see the justification for this, please look up necklaces, Lyndon words and de Bruijn sequences.
Write a function that takes a parameter n and then either prints or returns the de Bruijn sequence as either a character array string or instance of the std::string class. The character array will be of capacity $2^n + 1$ while the string will be of length $2^n$.
void de_bruijn_print( unsigned int n ); char *de_bruijn_array( unsigned int n ); std::string de_bruijn_string( unsigned int n );
Application
You can use this technique to create a de Bruijn sequence of order 10 of length 1024, which is sufficient to give each millimeter in a meter stick either a 0 (marked as black) or 1 (marked as white). The image in Figure 1 shows how the first 17 cm can be marked.
Figure 1. A ruler with millimeters marked with a de Bruijn sequence (black for 0 and the natural background for 1).
To see a full meter stick, click here.
Now, suppose you found that what you were measuring ended at the image shown in Figure 2.
Figure 2. A zoom on a gray object being measured.
We note that the black and natural markings past this gray object include 0001011101. A quick look-up of the de Bruijn sequence of order 10 indicates that it starts at entry 426, so the object in question must have been 42.6 cm long.
Incidentally, for your interest, here is the de Bruijn sequence constructed using the technique above with the sequence 0001011101 highlighted in red. If you look carefully, you will note that this sequence does not appear anywhere else in the 1024 bits.
0 0000000000 1000000001 1000000010 1000000011 1000000100
50 1000000101 1000000110 1000000111 1000001000 1000001001
100 1000001010 1000001011 1000001100 1000001101 1000001110
150 1000001111 1000010000 1000110000 1001010000 1001110000
200 1010010000 1010110000 1011010000 1011110000 1100010000
250 1100110000 1101010000 1101110000 1110010000 1110110000
300 1111010000 1111110001 0001010001 0001110001 0010010001
350 0010110001 0011010001 0011110001 0100110001 0101010001
400 0101110001 0110010001 0110110001 0111010001 0111110001
450 1000110010 1000110011 1000110100 1000110101 1000110110
500 1000110111 1000111001 1000111010 1000111011 1000111100
550 1000111101 1000111110 1000111111 1001001001 1001001010
600 1001001011 1001001101 1001001110 1001001111 1001010010
650 1001110010 1010110010 1011010010 1011110010 1100110010
700 1101010010 1101110010 1110110010 1111010010 1111110011
750 0011010011 0011110011 0101010011 0101110011 0110110011
800 0111010011 0111110011 1001110101 1001110110 1001110111
850 1001111010 1001111011 1001111101 1001111110 1001111111
900 1010101010 1110101011 0110101011 1110101101 0110111101
950 0111011101 0111101101 0111111101 1011011101 1011111101
1000 1101111101 1110111111 1111
Advanced exercise
1. Write a function
unsigned int *de_bruijn_lookup( unsigned int n );
That returns a dynamically-allocated array of capacity $2^n$, and given an $n$-bit number, this index within the array indicates where the corresponding sequence of bits within the de Bruijn sequence starts.
For example, the de Bruijn sequence of order 3 yields the values:
000 0
001 1
010 2
101 5
011 3
111 7
110 6
100 4
Thus, the returned array would be {0, 1, 2, 4, 7, 3, 6, 5}. Thus, for example, array[7] equals the value 5, indicating that 111 starts at bit 5 (where the first bit is bit 0).
2. De Bruijn sequences are not restricted to binary numbers. You can have bases (or alphabets). The principles, however, are the same. If the base is $m$, there a de Bruijn sequence of order $n$ has length $m^n$.
For example, $3^3 = 27$:
k smaller contribution
rotation to sequence
000 0
001 001
002 002
010 001
011 011
012 012
020 002
021 021
022 022
100 001
101 011
102 021
110 011
111 1
112 112
120 012
121 112
122 122
200 002
201 012
202 022
210 021
211 112
212 122
220 022
221 122
222 2
Thus, a base-3 de Bruijn sequence of order 3 is 000100201101202102211121222.
As another example, $4^2 = 16$:
k smaller contribution
rotation to sequence
00 0
01 01
02 02
03 03
10 01
11 1
12 12
13 13
20 02
21 12
22 2
23 23
30 03
31 13
32 23
33 3
Thus, a base-4 de Bruijn sequence of order 2 is 0010203112132233.
References
A de Bruijn sequence generator using the above algorithm: H. Kjellerstrand.
Department of Electrical and Computer Engineering
University of Waterloo
200 University Avenue West
Waterloo, Ontario, Canada N2L 3G1
Phone: +1 519 888 4567 extension 37023
Fax: +1 519 746 3077
Website maintained by Douglas Wilhelm Harder