Can you crack the combination lock? - Solution

The sequence 11221 contains all 2-digit combinations using the numbers 1 and 2.

A sequence such as that is called a De Bruijn sequence. I show you three methods to find such sequence. The first two involve making diagrams called graphs, and either taking a path that visits every node of a graph (a hamilton path), or a path that visits every edge of a graph (euler path). The third method is an algorithm for making 'Lyndon words' which if you string them together will make our De Bruijn sequence.

De Bruijn Sequences: http://en.wikipedia.org/wiki/De_Bruijn_sequence

Hamilton Path: http://en.wikipedia.org/wiki/Hamiltonian_path

Euler Path: http://en.wikipedia.org/wiki/Eulerian_path

Lyndon Words: http://en.wikipedia.org/wiki/Lyndon_word
There is an efficient method of generating a list of all Lyndon words of lengths that divide n, using the digits 1 to k, which involves a lot less crossing off. This is the method I used to make the final sequence in the video. I did not describe the method in the video, so let me describe it here:

Start the list with a sequence of n 1s, i.e. 11 . . . 1. We will generate successive words until we reach kk . . . k. For any word A = a1a2 . . . an, the successor of A is obtained as follows:

1. Let i be the largest value such that ai is less than k
2. Let B = a1a2 . . . ai-1(ai + 1)
3. Then the successor of A is the first n characters of BB . . . B.

We then decided to reject, replace, or keep the successor of A depending on the value of i:

1. If i does not divide n, the successor of A appears earlier on the list under rotation. Generate a successor to the word before removing it from the list.
2. If i divides n but not equal to n, the successor of A is periodic. Generate a successor to the word then replace BB . . . B with B. Replace 11 . . . 1 at the start of the list with 1.
3. If i = n we keep the successor of A.

This creates a list of Lyndon words, of lengths that divide n, written in lexicographic order.

Together, this list creates a De Bruijn sequence of length k^n, containing all the combinations of length n (if the sequence wraps around) using the digits 1 to k.
Ok then, here's an extra one for you to try. Use the algorithm to give me a sequence containing all 6-digit combinations using the numbers 1 and 2. So combinations like 111111, 112121, 211122 etc. The sequence is 64-digits long (if you let the sequence wrap back to the start).

Видео Can you crack the combination lock? - Solution канала singingbanana