chess:programming:de_bruijn_sequence:about_de_bruijn_sequences
This is an old revision of the document!
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
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).
References
chess/programming/de_bruijn_sequence/about_de_bruijn_sequences.1635429390.txt.gz · Last modified: 2021/10/28 13:56 by peter