1
$\begingroup$

Given all strings of length $k$ of an alphabet of size $n$. This gives $n^{k}$ strings. Now I want to create one superstring that contains all these strings as substrings. They hopefully strongly overlap such that the superstring is much shorter than $k n^{k}$.

The superstring should be as short as possible, given that the calculation of it should finish in polynomial time. So it might be not the shortest of all superstrings.

There are a lot of algorithms on the net for the shortest common superstring problem (as it is called) for a given set of substrings. This I could implement in Mathematica without problem. But I am interested for that special set described above, hoping that the algorithm simplifies considerably.

Question 1: Is there a function in Mathematica taht does this for me (so far my search was not successful.) ?

If there is no such built-in function, can someone sketch me how to implement it with Mathematica ? Or maybe give me a hint where to find literature on that problem ? Does it have a special name for a Google search

$\endgroup$
  • 4
    $\begingroup$ Sounds like you're after a De Bruijn sequence, perhaps with a few elements appended if it's not to be treated as circular. In any case, trivial to do in Mma with the eponymous graph... $\endgroup$ – ciao Jun 19 '15 at 10:01
  • $\begingroup$ @ciao that's it ! Thank you very much ! $\endgroup$ – Johannes Trost Jun 19 '15 at 10:27
  • $\begingroup$ Glad to help - BTW - if efficiency is paramount, look into using concatenated Lyndon Words - one can build the sequence in linear time and log space - though I'm not sure coding such a thing would beat the native MMA path finding and conversion since the former is done in low-level MMA code... $\endgroup$ – ciao Jun 19 '15 at 22:56
2
$\begingroup$

Is there a function in Mathematica that does this for me?

There is Experimental`ShortestSupersequence that works with pairs of lists or strings:

Experimental`ShortestSupersequence[{1, 4, 2}, {2, 4, 5}]

{1, 2, 4, 2, 5}

Experimental`ShortestSupersequence["142", "245"]

"12425"

You can Fold the function Experimental`ShortestSupersequence over the list of strings:

alphabet = CharacterRange["A", "K"];
k = 5;
lst = StringJoin /@ Tuples[alphabet, {k}];
Length@lst

161051

ss = Fold[Experimental`ShortestSupersequence, lst]

"ACDEFGHIJKBBCDEFGHIJKAACDEFGHIJKBBCDEFGHIJKAABCDEFGHIJK"

StringLength @ ss

55

k Length[alphabet]^k

805255

$\endgroup$

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.