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.
Answer
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: …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.
Attribution
Source : Link , Question Author : Chao Xu , Answer Author : Yuval Filmus