Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Substrings and superstrings

  1. Jun 27, 2005 #1

    StatusX

    User Avatar
    Homework Helper

    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.
     
  2. jcsd
  3. Jun 28, 2005 #2
    Is this homework?
     
  4. Jun 28, 2005 #3

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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 [itex]m!^n[/itex] but I don't remember the particulars.)
     
    Last edited: Jun 28, 2005
  5. Jun 28, 2005 #4

    StatusX

    User Avatar
    Homework Helper

    No. Try it and you'll see it's alot 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.
     
    Last edited: Jun 28, 2005
  6. Jun 28, 2005 #5
    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).
     
  7. Jun 28, 2005 #6

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    OK there is always a minimal loop:

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

    For [itex]n=1[/itex] this is the 'superstring'.

    Clearly, for [itex]n>1[/itex] 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 [itex]a_1,a_2,...a_m[/itex] in that order.
    Clearly any substring of the form [itex]a_2,a_3...a_{m},x_1[/itex] could be added there, so the loop could be broken there. Therefore, all subtrings of the form [itex]a_2,a_3...a_m,x_1[/itex] must be in the loop.
    Since any subtring of that form is in the loop, any substing of the form [itex]a_2,a_3...,x_1,x_2[/itex] must also be in the loop, otherwise it could be grafted on to theoccurance of [itex]a_2,a_3...x_1[/itex].
    This leads to the conclusion that any substring of the form [itex]x_1,x_2...x_m[/itex] must be in the loop, so the loop covers the entire space.
     
  8. Jun 28, 2005 #7
    What do you mean, "break open"? "Close"?
     
    Last edited: Jun 28, 2005
  9. Jun 28, 2005 #8

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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'.
     
  10. Jun 28, 2005 #9
    Define "break open." I don't know exactly what you mean from the example.
     
    Last edited: Jun 28, 2005
  11. Jun 28, 2005 #10

    StatusX

    User Avatar
    Homework Helper

    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?
     
    Last edited: Jun 28, 2005
  12. Jun 29, 2005 #11

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

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

    And, let's also assume that if
    [tex]S=s_1,s_2,s_3...s_k[/tex]
    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 [itex]0,0,...0[/itex]. Clearly, based on the second assumption it can be extended into a loop
    [itex]a_1,a_2...a_l,a_1,a_3...a_{m-1}[/itex]
    Now, if there is a suitable [itex]B=a_{o+1},a_{o+2}...a_{o+m-1},x[/itex]
    Then
    [itex]a_{o+m},a_{o+m+1}...a_{l},a_1,a_2...a_{o+1},a_{o+2}...a_{o+m-1},x[/itex]
    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 [itex]m^n+m-1[/itex] (or [itex]m^n[/itex] 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 [itex]m^n+m-1[/itex] times before terminating.

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

    So, we start with [itex]0,0,0[/itex] which is already a loop.
    But, we can find a 'suitable B': [itex]0,0,1[/itex]
    So we have:
    [tex]0,0,0,1[/tex]
    [tex]0,0,0,1,1[/tex]
    [tex]0,0,0,1,1,0[/tex]
    [tex]0,0,0,1,1,0,1[/tex]
    And, once again, there is a problem because we can't add any more symbols. At this point the only remaining B is [itex]1,1,1[/itex]
    So, rotate
    [tex]0,0,0,1,1,0,1 \rightarrow 0,1,0,0,0,1,1,[/tex]
    and append
    [tex]0,1,0,0,0,1,1,1[/tex]
    And this is the string
    [tex]0,1,0,0,0,1,1,1,(0,1)[/tex]
     
  13. Jun 29, 2005 #12

    StatusX

    User Avatar
    Homework Helper

    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.
     
  14. Jun 29, 2005 #13

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  15. Jun 29, 2005 #14

    StatusX

    User Avatar
    Homework Helper

    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.
     
    Last edited: Jun 29, 2005
  16. Jun 29, 2005 #15

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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).
     
  17. Jun 29, 2005 #16

    StatusX

    User Avatar
    Homework Helper

    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.
     
  18. Jun 30, 2005 #17

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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 [itex]2^4 = 16[/itex] 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?
     
  19. Jun 30, 2005 #18

    StatusX

    User Avatar
    Homework Helper

    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?

    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.
     
  20. Jun 30, 2005 #19

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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 untill 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...
     
  21. Jun 30, 2005 #20

    StatusX

    User Avatar
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?