Minimal Superpermutation Problem
Question Description
We have 1,2,…,n symbols. We want to find a shoretest possible string on the symbols that contains every permutation of those symbols as a contiguous substring. We call a string that contains every permutation in this way a superpermutation, and one of minimal length is called a minimal superpermutation.
For example, when n=3, all permutations are : 123,132,312,213,231,321. In this case, the minimal superpermutation is 123121321. The minimal length is 9.
Minimal Length
An apparent lower bound of the length of superpermutation on n symbols is n!+n−1, because it must contain every permutation of the n! permutations as a substring - the first permutation has n characters to the string, and each of the remaining n!−1 permutations have a lengh of at least 1 character more. A trivial upper bound on the length of a minimal superpermutation is n∗n!
Suppose we already have a small superpermutation on n and we want to construct a small superpermutation on n+1 symbols. To do so, simply replace each permutaiton in the n symbol superpermutation by (1) the permutaiton, (2)the symbol n+1 (3) that permutaiton again.
You can find detail here: link
Uniqueness
It turns out that there are in fact many superpermutations of the conjectured minimal lengh. The result of [1] shows that there are at least
∏n−4k=1(n−k−2)k⋅k!