What Is the Shortest String Containing All m-Digit Substrings Made of n Symbols?

[StatusX]

Find (for specific cases, or a general algorithm) the shortest string which contain as substrings all m digit strings made of n symbols. For example, for (2,2), the possible substrings are 00,01,10,11. One string of minimal length (which in general is n^m+m-1 digits) which contains all of these as substrings is 00110.

I don't know of a general algorithim to generate the minimal superstring, or even whether it always exists. One thing I've noticed, though, is that the superstrings always seem to end with the same m-1 digits they start with, (which you can exploit to generate many more solutions), but I haven't been able to prove this.

 

[BicycleTree]

Is this homework?

 

[NateTG]

It shouldn't be that hard to figure out that:
It's easy to extend any non-repeating partial superstring up to some length to make a minimal superstring.

There is a large number of possible minimal superstrings. (Something like $m!^n$ but I don't remember the particulars.)

 

[StatusX]

No. Try it and you'll see it's a lot harder than it looks. By the way here's some stuff if anyone wants it:

(2,3): 0011220210

(3,2): 0001011100

Proof of what I mentioned at the end of the first post, that the first m-1 digits are also the last m-1 digits:

Call the first (m-1) digits of the superstring A. The following strings must all appear exactly one time as substrings of the superstring: 0A, 1A, 2A,...,nA, (the xA) and A0, A1, A2,...,An (the Ax):. If A doesn't end the superstring, there need to be n copies of A throughout the superstring (including possible overlaps between copies of A. eg, if A=11, then there are 3 copies of A in 11122113.), one for each possible Ax. However, then there would only be (n-1) instances of xA (because one of the A's begins the superstring), and one of the strings above would not be included. The only way to add it without adding an extra Ax is to have an A at the end.

 

[BicycleTree]

Let's stop talking in white. This isn't like a quick brainteaser where you're worried about revealing answers.

Interesting. For binary and 3, I have 1100010111 and 0100011101. You can get four others from each of those by replacing 0 with 1 and vice versa, and by reversing the whole string, so I have 8 ways for that. Also for binary and 4 I got 1100001111010010110. Treating each 000, 001, 010, etc. as a two's complement binary number with 3 digits, the problem is the same as visiting each node exactly once of a graph where there is a directed edge between n and n*2, and between n and n*2+1, and between n and not(not(n)*2), and between n and not(not(n)*2+1).

 

[NateTG]

OK there is always a minimal loop:

Let's refer to the symbols as $0,1,...,n-1$ since there are finitely many, they can be aribitarily numbered.
Start with $0,0,0,,,,0$ ($m$ 0's.) This forms a 'loop' in that the trailing $m-1$ symbols, and the leading $m-1$ symbols are the same in the same sequence.

For $n=1$ this is the 'superstring'.

Clearly, for $n>1$ we can break open this loop, and start appending any symbols that would not lead to the repetition of a substring. It's easy to prove that the only times that if there are no legal symbols to append, the superstring is a loop.

That means that we can 'close the loop' and break it open somewhere else to add new symbols, if there are any unused substrings that would allow it.

Now, let's say that there are no places to 'break open' and extend the loop.

Clearly, we have, at some point in the parital, the symbols $a_1,a_2,...a_m$ in that order.
Clearly any substring of the form $a_2,a_3...a_{m},x_1$ could be added there, so the loop could be broken there. Therefore, all subtrings of the form $a_2,a_3...a_m,x_1$ must be in the loop.
Since any subtring of that form is in the loop, any substing of the form $a_2,a_3...,x_1,x_2$ must also be in the loop, otherwise it could be grafted on to theoccurance of $a_2,a_3...x_1$.
This leads to the conclusion that any substring of the form $x_1,x_2...x_m$ must be in the loop, so the loop covers the entire space.

 

[BicycleTree]

What do you mean, "break open"? "Close"?

 

[NateTG]

Let's say we're looking at 3 bit strings:
000 001 010 011 100 101 110 111

Now, something like:
0001(00)->
is a loop in the sense that it's the same as:
0010(00)->
or
0100(01)->

So if you think of it as a loop then you have to 'break' it open in order to splice stuff in
0100(01) -> 01001 -> 010011 -> 010011(01)

I don't know if that clarifies things. The symbols in parens represent 'overlap'.

 

[BicycleTree]

Define "break open." I don't know exactly what you mean from the example.

 

[StatusX]

I followed you up to the last paragraph. I also thought of these strings as loops, and you can generate many superstrings by starting at any point in the loop and repeating the first m-1 digits again at the end. But I can't figure out how you would add a digit at some point in the loop and be sure you wouldn't duplicate any of the m substrings it becomes a part of. Could you maybe illustrate your method with an example of how you could create a superstring with it?

 

[NateTG]

I followed you up to the last paragraph. I also thought of these strings as loops, and you can generate many superstrings by starting at any point in the loop and repeating the first m-1 digits again at the end. But I can't figure out how you would add a digit at some point in the loop and be sure you wouldn't duplicate any of the m substrings it becomes a part of. Could you maybe illustrate your method with an example of how you could create a superstring with it?

I'll try to be more formal:
Let's, assume, for a moment, that given a loop
$$A=a_1,a_2...a_k,a_1,a_2,...a_{m-1}$$
Claim:
There is either a substring
$$B=a_{o+1},a_{o+2}..a_{o+m-1},x$$
such that: $B$ is not in $A$
or
$A$ contains all of the possible substrings.

And, let's also assume that if
$$S=s_1,s_2,s_3...s_k$$
is a 'non-repeating partial superstring', that it is always possible to append symbols to it to form a loop.

So, let's start with an arbitrary 'non-repeating partial substring' - for example $0,0,...0$. Clearly, based on the second assumption it can be extended into a loop
$a_1,a_2...a_l,a_1,a_3...a_{m-1}$
Now, if there is a suitable $B=a_{o+1},a_{o+2}...a_{o+m-1},x$
Then
$a_{o+m},a_{o+m+1}...a_{l},a_1,a_2...a_{o+1},a_{o+2}...a_{o+m-1},x$
must be a larger 'non-repeating partial superstring' that the inital one and we can repeat the process.
Otherwise, we have the minimal non-repeating loop and we are done.

Since the number of symbols in a non-repeating loop is bounded above by $m^n+m-1$ (or $m^n$ depending on how you calculate loop length) and the process increases the length of the string by one symbol each iteration, it will run at most $m^n+m-1$ times before terminating.

For example, let's say we're looking at legth 3, 2-symbol strings.

So, we start with $0,0,0$ which is already a loop.
But, we can find a 'suitable B': $0,0,1$
So we have:
$$0,0,0,1$$
$$0,0,0,1,1$$
$$0,0,0,1,1,0$$
$$0,0,0,1,1,0,1$$
And, once again, there is a problem because we can't add any more symbols. At this point the only remaining B is $1,1,1$
So, rotate
$$0,0,0,1,1,0,1 \rightarrow 0,1,0,0,0,1,1,$$
and append
$$0,1,0,0,0,1,1,1$$
And this is the string
$$0,1,0,0,0,1,1,1,(0,1)$$

 

[StatusX]

But you're assuming that rotating will preserve the property that no substrings are repeated. What about the string 000110, for (3,2)? No substrings are repeated here, but rotating by one will leave two copies of 000. The problem is easy to fix here because this is a very simple case, but we need a completely general formula if we want to handle larger m and n values.

 

[NateTG]

But you're assuming that rotating will preserve the property that no substrings are repeated. What about the string 000110, for (3,2)? No substrings are repeated here, but rotating by one will leave two copies of 000. The problem is easy to fix here because this is a very simple case, but we need a completely general formula if we want to handle larger m and n values.

You chop off the overlap before you rotate. For example, if you start with
000110
You still add 0 (or actually 1) before you get into trouble:
0001100
Now the loop is really
00011
Which is what you rotate.

You're guaranteed to be able to close the loop for any non-repeating string, so you don't really lose any length when you do so.

 

[StatusX]

I understand what you're saying, but I don't think it will carry on to more complicated strings. When you add a digit, you aren't just adding a new substring and not affecting anything else. You are changing every substring within m digits of that spot. How can you be sure you aren't causing some substring to be duplicated or another to be removed?

For example, in (4,2), if the loop is 000011001(000), and you add a 1 in the middle to form 0000111001(000), you've added 0111 and 1110 but you've gotten rid of 0110.

 

[NateTG]

I don't care so much about losing substrings as long as I can keep making the partial longer until they're all there.

Regarding creating duplicates:
You can't create any new substrings on the left of the new symbol, and, if the string doesn't already loop, you're guaranteed to have unused substrings that allow you to close the loop. (It's pretty easy to prove).

 

[StatusX]

I'm not exactly sure what it is you're saying is easy to prove. Please feel free to show some of these easy proofs you've been mentioning. But in any case, your method, as I understand it, would come to a dead end on this string:

0010100001111(001)

I found this with a computer program I wrote, and there are probably simpler examples. There are no duplicates in this string, and yet there is no place to add a digit without creating a new loop which does have duplicates. Sorry if it feels like I'm attacking your idea, I just think this is a deeper, subtler problem and I'd be disappointed if it could be solved by such a simple, brute force approach.

 

[NateTG]

Sorry if it feels like I'm attacking your idea, I just think this is a deeper, subtler problem and I'd be disappointed if it could be solved by such a simple, brute force approach.

No, no, please keep chopping away. It keeps me honest, and improves my ability to explain things. That said, I'm quite sure that what I have in my head is valid, but I have a hard time describing it clearly.

Now:
Your loop is:
0010100001111(001)

Based on the (001) I would guess that we're looking at 4 bit strings, so there are $2^4 = 16$ of them. There are 13 substrings in the loop, so there are three missing. (0110, 1011, and 1101.)
I should be able to rotate to:
0000111100101(000)
'Chop off' the overlap
0000111100101
And add a 1
00001111001011
The following 0 is forced
000011110010110
And the following 1 is forced, and that's a minimal superstring.
0000111100101101(000)

P.S. What programming language are you using?

 

[StatusX]

And add a 1
00001111001011

But now there are two copies of 1100. True, there are no duplicates if you don't consider this as a loop, but what if you couldn't append another digit at the end here? You'd have to rotate the string and then there would be duplicates, loop or not.

Maybe I'm still misunderstanding your method. It seems to involve some on the fly thinking, stuff that a computer couldn't do. Could you maybe outline the structure of a program that would find the minimal string?

P.S. What programming language are you using?

It's a program called jamagic. It's not the best thing for something like this (it's designed for making 2D and 3D games), but it's all I had on this computer.

 

[NateTG]

OK.

Think of the process this way:
Start with a loop. For example the (00...0) substring.
If there are no unused substrings, then we are done.
Otherwise, there is some substring for which the first m-1 symbols match a section of the loop. (This requires a proof.)
Rotate the loop so that it 'ends' with the matching section (after chopping off the overlap) - at this point we cease treating it as a loop.
Append the last symbol of said unused substring.
Continue appending symbols that do not cause a repetition until there are no such symbols.
At this point the superstring will, once again, form a loop (this requires a proof) so the process can be restarted.

Note: Although the process 'looses' substrings from chopping off the overlap, the 'reformation' of a loop guarantees that it will regain at least as many substrings as it lost. With the extra symbol that is added, this means that the number of substrings covered by the process is strictly increasing unless all are covered. Since there is a finite number of them, the process must terminate.

This seems like it would be somewhat annoying to program...

 

[StatusX]

At this point the superstring will, once again, form a loop (this requires a proof) so the process can be restarted.

Alright, here is the assumption you've been making that I wasn't clear on. Do you have a proof in mind for this? If so, I think this is a promising idea.

 

[StatusX]

Ok, you're right. I found a proof for it: Call the last m-1 digits A. If there is no digit that can be added at the end of A without forming duplicates, there must be n other copies of A throughout the string, each with a different digit at the end. Then there are n+1 total copies of A, and since there are no duplicates, only n of these can have a space at the front, which means the superstring must start with A, and is therefore a loop.

Nice job. I'll look through the whole proof just to make sure, but it looks like you've proved the existence of a minimal superstring. I'm still going to look at this problem, though, to see if I can find any patterns in this process to come up with an algorithm that takes as few steps as possible.

 

[NateTG]

Nice job. I'll look through the whole proof just to make sure, but it looks like you've proved the existence of a minimal superstring. I'm still going to look at this problem, though, to see if I can find any patterns in this process to come up with an algorithm that takes as few steps as possible.

Are you trying to find all of them, or just one?

 

[StatusX]

Are you trying to find all of them, or just one?

Just a simple pattern that generates the minimal strings. For example, for (m,2), the strings, minus the tails, are: 1122, 11121222, ... It feels like there could a pattern there, and maybe for other n values as well.

But I just have one more question about your method. After you have a loop and chop off the final m-1 digits, you need to cycle the string until you find a spot where you can add more digits. For one thing, you could always add digits without cycling and get those m-1 digits back, so you need to specify that you can't do that. (I'm only saying this because I'm a little concerned about how complicated the algorithm is getting). But assuming you do choose a different path, how can you be sure that it won't terminate even sooner?

 

[NateTG]

But I just have one more question about your method. After you have a loop and chop off the final m-1 digits, you need to cycle the string until you find a spot where you can add more digits. For one thing, you could always add digits without cycling and get those m-1 digits back, so you need to specify that you can't do that. (I'm only saying this because I'm a little concerned about how complicated the algorithm is getting). But assuming you do choose a different path, how can you be sure that it won't terminate even sooner?

I specify that the first appended symbol is the one that adds a new substring. Any symbol that would lead to a shorter cycle, or a cycle of the same length, would requre that the substring was in the loop previously.

 

[StatusX]

Any symbol that would lead to a shorter cycle, or a cycle of the same length, would requre that the substring was in the loop previously.

How do you know that?

 

[NateTG]

Because the symbol is being added 'just before' the overlap. If the loop ends up being the same length, thent the new symbol must be part of the overlap, thus that substring must have been in the prior loop.

 

[StatusX]

Sorry to drag this on so long, but I want to make sure the proof is completely solid. Say you come to this string in (3,2):

0101110001

At this point, there's no digit you can add at the end, so you need to make it a loop and chop off the tail:

01011100(01) -> 01011100

Now you can add a 1 at the end to form:

010111001

This is a perfectly valid operation under your algorithm, but now we've got a new, shorter loop. If the length is no longer strictly increasing, I don't see how the proof can stand.

 

[NateTG]

Actually, and this may have been too subtle, the process requires that the first substring that you create is not in the previous loop - so what you did would not be legal according to the method I proposed.

 

[BicycleTree]

Also, "minimal" is not the right word. Every set of strings for given n, m has a minimal-length member, because the set of string lengths is a set of integers, which is well-ordered. A term like "theoretic minimal" would be more accurate.

Ah, reading the rest of StatusX's posts, I see he already said what I said in the previous two posts, now deleted.

 

[BicycleTree]

Because the symbol is being added 'just before' the overlap. If the loop ends up being the same length, thent the new symbol must be part of the overlap, thus that substring must have been in the prior loop.

How does that follow?

 

[BicycleTree]

I googled "superstring" and "substring" and it seems that finding the shortest common superstring of a set of substrings is not an unknown problem. StatusX, you never answered my question of whether this is homework.

 

[NateTG]

That does not follow. The so-called "extra symbol" may be part of the m-1 overlap symbols, generating a new string of only the same length.

Since appending that symbol at that point cannot, by construction, generate a substring that was in the loop (before the chop occured) it cannot be the first of the m-1 symbols of overlap - since, in order to be that, it would have to match a segment of the original loop.

That said, I'm not entirely sure I've covered the case where the situation is something like:
Pre-chop: 10(011)
Post-chop: 1(011)

So the algorithm doens't necessarily terminate.

 

[StatusX]

StatusX, you never answered my question of whether this is homework.

Yes I did. Its not.

 

[BicycleTree]

Note: I have edited and deleted some posts.

 

[BicycleTree]

Yes I did. Its not.

OK... but you didn't say it before.