Table of Contents
Chess - Programming - de Bruijn Sequence - About De Bruijn Sequences
Imagine a 4-digit PIN number.
- this means there can be 10,000 unique four-digit combinations, from 0000 to 9999.
- this also means 40,000 key presses.
Is there a quick way of going through all combinations without that number of key presses? Yes.
- By reusing what has already been entered previously.
NOTE: Simply look at just the last four keys pressed.
- Attempt 1: 1234 is entered.
- Attempt 2: Only a 7 is entered. The system sees the last four digits as 2347.
- Attempt 3: Only a 9 is entered. The system sees the last four digits as 3479.
So for Attempts 2 and 3, instead of 4 digits needing to be entered, only a single digits has been needed.
The big question “What is the shortest sequence of numbers that we can go through in order to ensure that all possible combinations of the digits are seen?”.
- Is it possible to create a sequence that does not repeat any sub-sequence of codes?
- This would be the most efficient.
- The answer is Yes, it is possible to make a non-repeating sequence of numbers that covers every sub-sequence internally, just once.
- This is a de Bruijn Sequence.
De Bruijn sequences; B(k,n)
De Bruijn sequences can be described by two parameters:
- k: the number of entities in the alphabet e.g. {0,1,2,3,4,5,6,7,8,9} for k=10
- n: the order (length of sub-sequence required) e.g. n=4 for a four digit long PIN.
NOTE: These are typically describe by the representation B(k,n).
- The PIN example above, the notation would be B(10,4).
Simple B(2,2)
A really simple example: B(2,2).
- The dictionary {0,1} will be used for the possible values.
To generate a string that contains sub-strings of each possible combination of two digits:
0011
NOTE:
- The first two digits give us 00,
- The next two 01
- Then 11.
- To get to 10, we need to Wrap Around taking the last digit from the string, and the first digit.
- This could also be accomplished by appending the first character from the string to the end to make 00110.
NOTE: There can be multiple De Bruijn solutions to any problem.
distinct solutions = (((k!)^k)^(n-1)) / (k^n)
- Since every adjacent pair of digits in the string is unique, it does not matter what the starting position is.
- As k and n increase, the number of possible solutions grows rapidly.
B(2,6)
Here is a solution for B(2,6):
0000001000011000101000111001001011001101001111010101110110111111
B(6,2)
Here is the output for B(6,2):
001020304051121314152232425334354455
NOTE: The size of the dictionary has been changed here.
- Rather than simple binary k=2, this is increased to k=6 to use possible values {0,1,2,3,4,5}.
- Reading this from left to right shows: 00, 01, 10, 02, 20 … 41, 15 … 33, 34 … 55, 50
- this 50 at the end is comprised of the last 5 and the first 0.