Can you crack the combination lock? - Solution





The interactive transcript could not be loaded.



Rating is available when the video has been rented.
This feature is not available right now. Please try again later.
Uploaded on Dec 13, 2011

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_Bruij...

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

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

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).

  • Category

  • License

    • Standard YouTube License


to add this to Watch Later

Add to