Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I would like to construct a length $N$ string over a $k$-letter alphabet, $S$, such that any substring of $P$ sequential characters in $S$ is unique for as small a value of $P$ as possible. To clarify, "unique" means that the fixed-length substring or its transpose occurs at most once in $S$.

For fixed $N$ and $k$, what is the smallest possible value of $P$, and how do I construct $S$ in such a manner as to minimize $P$?

share|improve this question
    
I can't parse this question. I don't know what it means for a substring to be unique - I suppose you mean you want to minimize the value of $P$ such that no substring of length $P$ appears twice? I don't know what "between any substring" means. Usually, "between" takes two objects - between such-and-such and somehting else. Also, you're trying to minimize one thing while at the same time maximizing something else, which seems like asking the impossible. Maybe an example or three would clarify things. –  Gerry Myerson Sep 6 '11 at 3:38
    
@Gerry, "Also, you're trying to minimize one thing while at the same time maximizing something else, which seems like asking the impossible." - fair criticism, I've removed the optimization component of the problem. As for "between any substring" I mean any pair of fixed-length arbitrarily selected substrings in 'S'. Hopefully I clarified in the above problem what I meant by "unique". –  H.H. Sep 6 '11 at 16:22
    
This might be relevant: en.wikipedia.org/wiki/De_Bruijn_sequence –  leonbloy Sep 6 '11 at 17:28
    
What is the "transpose" of a string? –  Gerry Myerson Sep 7 '11 at 1:59
    
Perhaps math.stackexchange.com/questions/15510/… is of interest. –  Gerry Myerson Sep 7 '11 at 2:01

1 Answer 1

If P is odd, there are $\frac{k^P}{2}+\frac{k^\left({\frac{P+1}{2}}\right)}{2}$ distinct substrings (avoiding transpositions). If P is even, there are $\frac{k^P}{2}+\frac{k^\left({\frac{P}{2}}\right)}{2}$. $N$ must be at most this plus $P-1$. Constructing such a string shouldn't be hard, but I don't have an algorithm. Maybe this naive algorithm will work-append a character that doesn't produce a duplicate substring and within those, the one used least so far.

share|improve this answer
    
thanks for your answer! My main interest here, and the difficulty I'm having, is in finding an algorithm that is guaranteed to construct optimal 'S'... –  H.H. Sep 7 '11 at 5:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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