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 kcombinations 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 k
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!