2
$\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$
3
  • 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$ 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
3
$\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$
2
  • 1
    $\begingroup$ Unfortunately, in general, 𝘯-ary shortest common supersequence cannot be obtained by iteratively folding a list of strings with a 2-ary function computing shortest common supersequence of 2 strings at each step; to get a correct result, the algorithm needs access to all input strings, not just to one input string and a partial result at each step. E.g., Fold[Experimental`ShortestSupersequence, {{2, 4, 3}, {2, 1, 0}, {2, 3, 1, 0}}] returns {2, 4, 3, 1, 3, 0}, while there is a shorter common supersequence {2, 4, 3, 1, 0}. $\endgroup$ Jun 22 at 17:34
  • $\begingroup$ @VladimirReshetnikov, excellent point. Perhaps, we can use 2-ary Experimental`ShortestSupersequence in a loop over permutations of the input list, e.g., First@MinimalBy[Length] @ DeleteDuplicates[ Fold[Experimental`ShortestSupersequence, #] & /@ Permutations[{{2, 4, 3}, {2, 1, 0}, {2, 3, 1, 0}}]]? $\endgroup$
    – kglr
    Jun 22 at 17:43

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.