What is the shortest string that contains all permutations of an alphabet?

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 n1 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 n2 characters, followed by the usual rotation of n1 characters. Now we get back to the earlier operation (rotation of n1), applying occasionally the new rotation, until we get stuck; we would then need to do a rotation of the middle n3 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

Leave a Comment