In combinatorialmathematics, a superpermutation on n symbols is a string that contains each permutation of n symbols as a substring. While trivial superpermutations can simply be made up of every permutation listed together, superpermutations can also be shorter because overlap is allowed. For instance, in the case of n = 2, the superpermutation 1221 contains all possible permutations, but the shorter string 121 also contains both permutations. It has been shown that for 1 ≤ n ≤ 5, the smallest superpermutation on n symbols has length 1! + 2! + … + n!. The first four smallest superpermutations have respective lengths 1, 3, 9, and 33, forming the strings 1, 121, 123121321, and 123412314231243121342132413214321. However, for n = 5, there are several smallest superpermutations having the length 153. One such superpermutation is shown below, while another of the same length can be obtained by switching all of the fours and fives in the second half of the string : 12345123415234125341235412314523142531423514231542312453124351243152431254312 1345213425134215342135421324513241532413524132541321453214352143251432154321 For the cases of n > 5, a smallest superpermutation has not yet been proved nor a pattern to find them, but lower and upper bounds for them have been found.
Finding superpermutations
One of the most common algorithms for creating a superpermutation of order is a recursive algorithm. First, the superpermutation of order is split into its individual permutations in the order of how they appeared in the superpermutation. Each of those permutation are then placed next to a copy of themselves with an nth symbol added in between the two copies. Finally, each resulting structure is placed next to each other and all adjacent identical symbols are merged. For example, a superpermutation of order 3 can be created from one with 2 symbols; starting with the superpermutation 121 and splitting it up into the permutations 12 and 21, the permutations are copied and placed as 12312 and 21321. They are placed together to create 1231221321, and the identical adjacent 2s in the middle are merged to create 123121321, which is indeed a superpermutation of order 3. This algorithm results in the shortest possible superpermutation for all nless than or equal to 5, but becomes increasingly longer than the shortest possible as n increase beyond that. Another way of finding superpermutations lies in creating a graph where each permutation is a vertex and every permutation is connected by an edge. Each edge has a weight associated with it; the weight is calculated by seeing how many characters can be added to the end of one permutation to result in the other permutation. For instance, the edge from 123 to 312 has weight 2 because 123 + 12 = 12312 = 312. Any hamiltonian path through the created graph is a superpermutation, and the problem of finding the path with the smallest weight becomes a form of the traveling salesman problem. The first instance of a superpermutation smaller than length was found using a computer search on this method by Robin Houston.
An algorithm for finding the smallest superpermutation for 6 or more symbols is as of yet unsolved. However, several proofs have gradually shrunk the strong upper and lower bounds of the problem over time.
Lower bounds, or the Haruhi problem
In September 2011, an anonymous poster on the Science & Math board of 4chan proved that the smallest superpermutation on n symbols has at least length n! + ! + ! + n − 3. In reference to the Japanese anime series The Melancholy of Haruhi Suzumiya, the problem was presented on the imageboard as "The Haruhi Problem": if you wanted to watch the 14 episodes of the first season of the series in every possible order, what would be the shortest string of episodes you would need to watch? The proof for this lower bound came to the general public interest in October 2018, after mathematician and computer scientist Robin Houston tweeted about it. On 25 October 2018, Robin Houston, Jay Pantone, and Vince Vatter posted a refined version of this proof in the On-Line Encyclopedia of Integer Sequences. For "The Haruhi Problem" specifically, the lower bound is currently at least 93,884,313,611, and the upper bound is at most 93,924,230,411.
Upper bounds
On 20 October 2018, by adapting a construction by Aaron Williams for constructing Hamiltonian paths through the Cayley graph of the symmetric group, Greg Egan devised an algorithm to produce superpermutations of length n! + ! + ! + ! + n − 3. Up to 2018, these were the smallest superpermutations known for n ≥ 7. However, on 1 February 2019, Bogdan Coanda announced that he had found a superpermutation for n=7 of length 5907, or ! + ! + − 1, which was a new record. On 27 February 2019, using ideas developed by Robin Houston, Egan produced a superpermutation for n = 7 of length 5906. Whether similar shorter superpermutations also exist for values of n > 7 remains an open question.
