De Bruijn sequences

I recently came across an interesting problem :-

Given a combination lock with a key of length n, we’ve to find the smallest string of digits which has every possible key as its substring. (Here we use all digits from 0 to 9 ; a general form of the problem would be to use k keys 0 to k-1). 
This wikipedia article – De Bruijn Sequences explains the concept
Basically, given n and k, we’ve to find a sequence in which every possible combination of n digits occur exactly once. Some people like to denote it as B(n,k).
Have a look at the following astonishing video, and then we’ll discuss a few details.
Talking about the first method he describes, which is an amazing visualisation of the problem as a graph. We consider each of the kn combinations as a node of the graph. We draw an edge between two nodes if it is possible to convert one node to another by changing the last digit. Then the problem is reduced to precisely visiting each node of the graph once. Since we want to reduce the size of final string, the most ideal situation would be if we can find a path in which each node is visited only once. Turns out, such a path always exist. We’ll prove it soon.
Now, talking about the problem of visiting each node once and covering all the nodes, such a path is called Hamiltonian path. Here is a link for your reference. The sad part is, finding a Hamiltonian path is NP complete problem. And so, we shift to the second method described in the video using eulerian paths. Interestingly enough, finding eulerian path is linear complexity algorithm. We describe the nodes as kn-1
combinations of the n-1 numbers. There are k outgoing and k incoming edges for each node in the graph, which makes it possible to construct the eulerian path. Each edge adds a character to our final string to be reported.
Do give this pdf a read to understand the proof behind the existence of eulerian path. If you are interested to write a program finding the eulerian paths, there is an algorithm called Hierholzer’s algorithm.
I like the problem and the smart way of visualising it as graphs. The innovations and ideas of man never ceases to amaze me and this solution is one such example. Have a good day!

Published by Mayank

Heyy, I am your friend Mayank. Loves talking about photography, tech, politics, and combinatorics. Hit me up if you got a puzzle xD

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create your website with WordPress.com
Get started
%d bloggers like this: