42
$\begingroup$

What is the shortest string $S$ over an alphabet of size $n$, such that every permutation of the alphabet is a substring of $S$?

I thought of this problem while reading a open problem on shortest supersequence of all permutations.

  • 0
    Which definition of substring are you using?2010-12-25
  • 4
    @Qiaochu: A substring of a string is a prefix of a suffix of the string2010-12-25
  • 0
    The length of this string (_Minimum length of a string of letters that contains every permutation of n letters as sub-strings, also known as length of the minimal super-permutation._) is known as the A180632 sequence in the [OEIS](http://oeis.org/A180632). Although there has been progress since the question was posed (follow the link), not even the exact length is known, let alone a construction.2018-12-23

3 Answers 3