What is the shortest string $S$ over an alphabet of size $n$, such that every permutation of the alphabet is a substring of $S$?
Edit 2019-10-17: This is called a superpermutation, and there is a wikipedia page that keeps track of the best results. Turns out the problem is still open.
Here are some thoughts: given a permutation $abcde$, you can generate all its cyclic rotations with no additional cost: $abcdeabcd$. Then you'd want to capitalize of the largest number symbols, so we repeat the deepest symbol, in this case $a$, complete the permutation with $e$, and generate all cyclic rotations: $abcdeabcdaebcda$. So far we've generated all cyclic rotations of $abcde$ and $bcdae$. Notice that the first $n-1$ characters are rotated. We continue to generate all cyclic rotations of $cdabe,dabce$, and then we have to bring back one symbol shallower: $\ldots dabcedabcadebcad$. So we moved from $dabce$ to $bcade$. This corresponds to rotation of the middle $n-2$ characters, followed by the usual rotation of $n-1$ characters. Now we get back to the earlier operation (rotation of $n-1$), applying occasionally the new rotation, until we get stuck; we would then need to do a rotation of the middle $n-3$ characters, and so on.
I would conjecture that the preceding scheme is optimal; the diligent reader can recursively calculate its length.
I researched this question 20 years ago and found that the length of the shortest string containing all the permutations of n objects to be as stated in http://www.notatt.com/permutations.pdf. We created a computer algorithm to generate all possible strings containing all permutations of n objects and proved this minimal length through brute force for alphabets up to 11 objects. We never could find a proof that our algorithm generated the shortest strings for any n and I would love for someone to pick this subject up. I've found that most mathematicians disregard this topic as already done when in fact, upon close examination, it has not been proven. If anyone knows of such a proof, please pass it along. You can find our paper at Minimal Superpermutations, Ashlock D., and J. Tillotson, Congressus Numerantium 93(1993), 91-98.
[NB] This argument as stated is incorrect, and the error is pointed out by Yuval in the comments below. One can indeed use the De Bruijn graph to get all permutations, exactly as I described below, but as Yuval's comment implies, one will also get plenty of non-permutations. The length of the string $S$ is not what my argument says it is, and the problem of the MINIMAL LENGTH sequence seems to require a different argument.
Since there are $n!$ permutations of $n$ symbols, the string $S$ must have length at least $n!+n-1$. That is, there must be $n!$ starting positions for a permutation, and the last starting position must be succeeded by $n-1$ symbols.
There is in fact such a string, which is obtained from an Eulerian path in the De Bruijn graph $B(n,n)$. This is a directed graph whose vertices are all strings of $n-1$ distinct symbols, with a directed edge from $u$ to $v$ if there is a symbol $s$ such that $v$ has the form $u_1s$, where $u_1$ is $u$ with the left-most symbol deleted. We label the edge with $s$. Every vertex has the same in-degree and out degree so the graph has an eulerian path. The labels of the edges on any such path, together with the string where the path ends, gives a minimal sequence of the kind you want. See this Wikipedia article http://en.wikipedia.org/wiki/De_Bruijn_sequence for terminology, references and a nice explanation.
