De Bruijn sequence
A De Bruijn sequence is the sequence of characters which can represent all possible character combinations of a specified length from a given alphabet. This is used to compress a large set of possible combinations into the shortest possible amount of space. For example, to list all of the possible combinations of an alphabet consisting of the characters A, B, and C, with a combination length of two, you would need 18 characters: AA, AB, AC, BA, BB, BC, CA, CB, and CC. However, the De Bruijn sequence which includes all of those combinations would only be nine characters: AABACBBCC. You may notice that CA is not part of the sequence, but the De Bruijn sequence is expected to wrap from the end to the beginning, which includes CA.
Applications
Data Compression
Because a De Bruijn sequence can greatly reduce the space needed to list all possible combinations of a series of values, you can replace a complete list of possible combinations with its De Bruijn sequence, and then point to a place value to obtain the value.
Computers
Especially useful in computers is the De Bruijn sequence for all the combinations of a byte. A byte can be described an alphabet of two characters (0 or 1) with a combination length of eight. To list all possible combinations of a byte requires 2,048 characters, however, the De Bruijn sequence is only 256 characters long:
00000000 10000001 10000010 10000011 10000100 10000101 10000110 10000111 10001000 10011000 10101000 10111000 11001000 11011000 11101000 11111001 00101001 00111001 01011001 01101001 01111001 10011010 10011011 10011101 10011110 10011111 10101010 11101011 01101011 11101101 11101110 11111111
Cryptography
A De Bruijn sequence can greatly increase the speed of a brute force attack if the gateway processes keys based on the most recent data. For example, most early garage door openers merely compared the last eight bits they received with their internal key, and, if they matched, opened. Thus, you can send a non-stop De Bruijn sequence and be guaranteed entry.
For an example of this in action, see this Veritasium video.
Games
In addition to simply determining the De Bruijn sequence, several games have been made based on it. For example, there is a series of puzzles in the game Nelson Tethers: Puzzle Agent called "A Quorum of Crows" where several photographs of birds on a wire need to be line up to get as close to a De Bruijn sequence as possible.
Links
- en.wikipedia.org/wiki/De_Bruijn_sequence - Wikipedia.
- mathworld.wolfram.com/deBruijnSequence.html - Wolfram MathWorld.
