Upload

Loading icon Loading...

This video is unavailable.

Can you crack the combination lock? - Solution

Sign in to YouTube

Sign in with your Google Account (YouTube, Google+, Gmail, Orkut, Picasa, or Chrome) to like singingbanana's video.

Sign in to YouTube

Sign in with your Google Account (YouTube, Google+, Gmail, Orkut, Picasa, or Chrome) to dislike singingbanana's video.

Sign in to YouTube

Sign in with your Google Account (YouTube, Google+, Gmail, Orkut, Picasa, or Chrome) to add singingbanana's video to your playlist.

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

Loading icon Loading...

Loading icon Loading...

Loading icon Loading...

The interactive transcript could not be loaded.

Loading icon Loading...

Loading icon Loading...

Ratings have been disabled for this video.
Rating is available when the video has been rented.
This feature is not available right now. Please try again later.

Loading icon Loading...

Loading...
Working...
to add this to Watch Later

Add to