21
$\begingroup$

There was a question in a math competition that I attended last year. At the end of competition, I realized that my answer was wrong for the question below and I have never been able to figure out how to solve it.

Here is the question:

You are asked to generate 10 digit strings using digits from 0 to 9 once each. Any four-digit substring used in a string cannot be used again.

What is the highest number of unique strings you can generate using these rules? (and I need the list of them)

Example:

If you use a string 0243697518 in your list, you can not generate strings contain 0243, 2436, 4369, 3697, 6975, 9751 and 7518

To solve the problem, I have written a c++ program, simply it scans all permutation of "0123456789" and add them into a solution list if 4 digit sub-strings of the code has not been used before. But the problem of my algorithm is that the size of solution list varies by depending on your starting point that you add into the list first. If I start adding into list from "0123456789", list ends up with 504 entries which is not the maximum asked. I really wonder how to solve this question, any help highly appreciated. I'm open to hear your mathematical solution or any algorithm suggestions to generate the list asked.

Histogram of random approach as suggested by Peter (min: 575, max: 606):

Above algorithm tries to generate list asked by scanning all possible 10 digit strings in a random sequence. Histogram generated over 100K trials. Because all possible 10 digits strings needed to be scanned for each iterations are 10! = 3.6 million, each iterations takes 10 seconds on my pc to complete. I could try optimizing my algorithm more if I believed that there was really no deterministic solution for the question.

$\endgroup$
  • 2
    $\begingroup$ It couldn't be any more than $720$. To get $720$, you have to use every possible $4$-digit string. $\endgroup$ – bof Oct 29 '14 at 13:28
  • 1
    $\begingroup$ This seems to be a kind of packing problem. Such problems usually are difficult to solve. $\endgroup$ – Peter Oct 29 '14 at 13:50
  • 1
    $\begingroup$ Perhaps, the naive approach (choosing randomly) produces a solution in reasonable time. Simply try it. $\endgroup$ – Peter Oct 29 '14 at 14:40
  • 1
    $\begingroup$ Not quite practical as a computational solution, but this can be reduced to the independent set problem on a graph of $10!$ nodes and $\frac{10! 7!}{2}$ edges. $\endgroup$ – Peter Taylor Oct 30 '14 at 10:54
  • 1
    $\begingroup$ Independent set problem $\endgroup$ – Peter Taylor Oct 30 '14 at 12:25
3
+50
$\begingroup$

The de Bruijn sequence gives you approximately 1428 possibilities (10000/7 plus or minus one or two due to rounding): shift a window of size 10 through it, each time shifting by 3 positions.

Edit (sorry, I also missed the part that you want permutations). This might bring you a bit closer to what you need: "Universal cycles of k-subsets and k-permutations" by B.W. Jackson, and also look for newer papers and books citing this paper (for example, in Google scholar). By building an Eulerian walk in a suitable graph you can generate a cycle containing each partial 4-permutation exactly once, something called a universal cycle (ucycle) of partial permutations.

$\endgroup$
  • $\begingroup$ This allows repetition of digits; the OP does not. $\endgroup$ – Empy2 Nov 1 '14 at 18:31
  • $\begingroup$ I don't know where that 10000 comes from. But I had tried both De Bruijn and Kautz sequences similar to each other before. B(4, 10) generates unique sequence of 4 digits. When I combine them in order to generate 10 digits, characters inside are not being unique anymore. $\endgroup$ – Mehmet Fide Nov 1 '14 at 18:33
2
$\begingroup$

Instead of iterating between 10-digit numbers, make a list of all the possible 4-digit numbers (which are $10*9*8*7=5040$ and merge 7 4-digit numbers at a time to obtain 10-digit numbers. It is a dynamic programming question and you will have to backtrack to get already used 4-digit numbers into 10-digit numbers that require them the most. Using this approach, the maximum possible 10-digit strings should be $(10*9*8*7)/7=720$.

$\endgroup$
  • $\begingroup$ Well the problem here is that each digits are unique. So it is not 10000, it is 10x9x8x7=5040. I've heard about algorithms you mentioned, but I don't have any practical abilities on them. I need to study. $\endgroup$ – Mehmet Fide Nov 1 '14 at 18:44
  • $\begingroup$ Sorry, I didn't notice the part that digits are unique within a string. I've edited my answer. $\endgroup$ – ghosts_in_the_code Nov 3 '14 at 16:12
  • $\begingroup$ You should edit "..merge 7 4-digit numbers at a time to obtain 10-digit numbers" section as well. Because it is not easy to merge 4-digit numbers anymore. $\endgroup$ – Mehmet Fide Nov 3 '14 at 16:42
0
$\begingroup$

I don't have a solution but here are some thoughts on the problem. We can look at the $(m,n)$ of finding the maximum possible number of strings of $m$ symbols with no strings of length $n$ used more than once in the whole set of strings. We can construct a graph $G$ whose vertices $V$ are the $n$-digit strings. We'll put an edge between two vertices $v$ and $v'$ if the strings overlap in the following way

$$v = s_1 s_2 \ldots s_n, \quad v' = s_2 \ldots s_n s_{n+1}$$

where $s_1 \neq s_{n+1}$. We connect every vertex $v$ to $m-n$ other vertices. Also every vertex has $m-n$ edges leading to it. Overall

$$|V| = n!\binom{m}{n} = \frac{m!}{(m-n)!},\quad |E| = (m-n)|V| = \frac{m!}{(m-n-1)!}$$

We can represent each $m$-digit string by a directed path in $G$ of length $m-n$, containing $m-n+1$ vertices. We need to find the maximum number of such vertex-disjoint paths in $G$. One would have a theoretical maximum of

$$\frac{m!}{(m-n+1)!}$$

such paths if all the vertices are used. In your case of $m = 10$, $n = 4$ you have 720 possible paths and from the problem you know you can find this many paths. This corresponds to finding a vertex cover of $G$ consisting of paths of vertex length 7. If anyone knows of an algorithm to find such a cover, then they can apply it to this problem. This is not always the case though. For $m = 3$ and $n = 2$ you'd expect $6/2 = 3$ such paths but the graph $G$ consists of 2 disjoint directed 3-cycles.

Clearly, the graph $G$ has to remain invariant by any permutation of the digits themselves, so one could easily set one of the paths in the cover as $0123\to 1234 \to \cdots \to 6789$.

Another thing to note is that if we can find a Hamiltonian cycle in the graph we can delete every $m-n+1$-th edge to obtain such a maximal cover if one exists. Unfortunately I don't have an algorithm for finding Hamiltonian cycles in a directed graph but someone else might.

$\endgroup$
  • $\begingroup$ Here is the hamiltanian cycle for the graph has 5040 vertices: ( files.figshare.com/1780575/Hamiltonian_Cycle.txt ) A means 0, B means 1, etc.. But it doesn't help because when you merge them, you will find repeating digits in combined 10 digit strings. So solution way should be something else. $\endgroup$ – Mehmet Fide Nov 9 '14 at 8:16
  • $\begingroup$ You mean there are repeating 4-digit strings? $\endgroup$ – Alexander Vlasev Nov 9 '14 at 8:17
  • $\begingroup$ Ahh, you don't have the right graph. From the start you have BCDA, CDAB where B repeats. In my graph I've put the edges only when the first digit of the first vertex is not the same as the last digit of the end vertex. The resulting graph is sparser than what you will get if you only put edges for the overlaps. $\endgroup$ – Alexander Vlasev Nov 9 '14 at 8:28
  • $\begingroup$ For example this is the part of cycle found. "1230 -> 2301 -> 3014 -> 0143 -> 1430 -> 4305 -> 3054 -> 0543 -> 5436 -> 4365 -> 3654 -> 6542.." Lets combine them to make 10 digits: 123014305436542... See first 10 digit after merging them, there are not unique. They are uniqe only in 4 digits window. $\endgroup$ – Mehmet Fide Nov 9 '14 at 8:29
  • $\begingroup$ Did you see my response? Could you try this with the modified graph? $\endgroup$ – Alexander Vlasev Nov 9 '14 at 8:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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