Let's consider all 4 digits sequences:

0000
0001
0002
...
9999

Obviously there is a large sequence containing all of them as substrings (the concatenation of all of them).

My question is, what is the length of the smallest possible such sequence (since the minimum is attained)?

For 1 digit, the answer is clearly :

0123456789

(or any permutation).

For 2 digits numbers, it it can be shortened, since "001" contains both "00" and "01".

But I have no clue on how to get to a definitive answer.

I spotted this similar question, but I'm not interested in the permutations of the alphabet, but 4-sequences.

  • do you know if there is a known answer to find, or has it otherwise cropped up? If we do find a short representation, I wonder how it could be proved to be the shortest. – Cato Feb 6 '17 at 10:14
  • I actually don't know. I know the answer exists, but I'm not sure there is a constructive one, or even a computable one – Regis Portalez Feb 6 '17 at 10:16
  • I agree there is an answer, it is maybe possible to get the 2 digit solution with a desktop computer - 4 digits, I don't know though – Cato Feb 6 '17 at 10:19
up vote 1 down vote accepted

This is very closed to De Bruijn sequences.


Let's call $A$ your alphabet (for decimal numbers $A=\{0,\ldots,9\}$) and $n$ the length of the contained sequences. We look for sequences containing all elements as (possibly) cyclic substring.

Consider the digraph $G = (V,E)$, where:

$$V=A^{n-1}$$ $$E=\{((u_1, \ldots, u_{n-1}), (u_2, \ldots, u_{n-1}, v)), (u_1,\ldots, u_{n-1},v \in A^n\}$$

Then sequences containing all elements of $A^n$ as substring are exactly walks in $G$ going through every edge.

Each node has an in and out degree of $|A|$, so this graph has an Eulerian cycle, which leads to a sequence of length $|A|^n$ minimal possible.


If we delete the cycle, the same graph still works. However, the minimal length we get is now the cost of writing the $n-1$ first letters plus the $|E|$ edges, i.e. $n-1+|A|^n$. For $n=4$, $A=\{0,\ldots,9\}$, we get $10003$.

  • Very interesting. Thanks. – Regis Portalez Feb 6 '17 at 16:15
  • Surprisingly short by the way. In three hours I can break a 4 digits pin ;) – Regis Portalez Feb 6 '17 at 18:59

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.