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