# Shortest Common Superstring for all k-length strings on an alphabet

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

• 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...
– ciao
Commented Jun 19, 2015 at 10:01
• @ciao that's it ! Thank you very much ! Commented Jun 19, 2015 at 10:27
• 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...
– ciao
Commented Jun 19, 2015 at 22:56

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

There is ExperimentalShortestSupersequence that works with pairs of lists or strings:

ExperimentalShortestSupersequence[{1, 4, 2}, {2, 4, 5}]


{1, 2, 4, 2, 5}

ExperimentalShortestSupersequence["142", "245"]


"12425"

You can Fold the function ExperimentalShortestSupersequence over the list of strings:

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


161051

ss = Fold[ExperimentalShortestSupersequence, lst]


"ACDEFGHIJKBBCDEFGHIJKAACDEFGHIJKBBCDEFGHIJKAABCDEFGHIJK"

StringLength @ ss


55

k Length[alphabet]^k


805255

• 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[ExperimentalShortestSupersequence, {{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}. Commented Jun 22, 2021 at 17:34
• @VladimirReshetnikov, excellent point. Perhaps, we can use 2-ary ExperimentalShortestSupersequence in a loop over permutations of the input list, e.g., First@MinimalBy[Length] @ DeleteDuplicates[ Fold[ExperimentalShortestSupersequence, #] & /@ Permutations[{{2, 4, 3}, {2, 1, 0}, {2, 3, 1, 0}}]]?
– kglr
Commented Jun 22, 2021 at 17:43