Differences

This shows you the differences between two versions of the page.

--- chess:programming:de_bruijn_sequence:about_de_bruijn_sequences [2021/10/28 13:49] – created peter
+++ chess:programming:de_bruijn_sequence:about_de_bruijn_sequences [2021/10/28 14:19] (current) – [Chess - Programming - de Bruijn Sequence - About De Bruijn Sequences] peter
@@ Line 20: / Line 20: @@
 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.
+  * See [[Chess:Programming:de Bruijn Sequence:About De Bruijn Sequences:The shortest sequence of numbers for the 4-digit PIN|The shortest sequence of numbers for the 4-digit PIN]]
 </WRAP>
 ----
+===== 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.
+<WRAP info>
+**NOTE:**  These are typically describe by the representation **B(k,n)**.
+  * The PIN example above, the notation would be **B(10,4)**.
+</WRAP>
+----
+===== 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:
+{{:chess:programming:de_bruijn_sequence:de_bruijn_sequences_-_b2-2.png?200|}}
+<code bash>
+</code>
+<WRAP info>
+**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.
+</WRAP>
+<WRAP info>
+**NOTE:**  There can be multiple De Bruijn solutions to any problem.
+<code>
+distinct solutions = (((k!)^k)^(n-1)) / (k^n)
+</code>
+  * 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.
+</WRAP>
+----
+===== B(2,6) =====
+Here is a solution for B(2,6):
+<code>
+0000001000011000101000111001001011001101001111010101110110111111
+</code>
+----
+===== B(6,2) =====
+Here is the output for B(6,2):
+<code bash>
+001020304051121314152232425334354455
+</code>
+<WRAP info>
+**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.
+</WRAP>
+----
 ===== References =====
 https://datagenetics.com/blog/october22013/index.html