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$:
We can make some observations:
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 );
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
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.
A de Bruijn sequence generator using the above algorithm: H. Kjellerstrand.