Superpermutation

The distribution of permutations in a 3-symbol superpermutation

In combinatorial mathematics, 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 concatenated together, superpermutations can also be shorter (except for the trivial case of n = 1) because overlap is allowed. For instance, in the case of n = 2, the superpermutation 1221 contains all possible permutations (12 and 21), 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! (sequence A180632 in the OEIS). 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 (after the bold 2):

12345123­41523412­53412354­12314523­14253142­35142315­42312453­12435124­31524312­54312134­52134251­34215342­13542132­45132415­32413524­13254132­14532143­52143251­432154321

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

A diagram of the creation of a superpermutation with 3 symbols from a superpermutation with 2 symbols

One of the most common algorithms for creating a superpermutation of order $n$ is a recursive algorithm. First, the superpermutation of order $n-1$ 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 n less 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 (dropping the same number of characters from the start) 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 $1!+2!+\ldots +n!$ was found using a computer search on this method by Robin Houston.

Lower bounds, or the Haruhi problem

In September 2011, an anonymous poster on the Science & Math ("/sci/") board of 4chan proved that the smallest superpermutation on n symbols (n ≥ 2) has at least length n! + (n−1)! + (n−2)! + 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 (OEIS). A published version of this proof, credited to "Anonymous 4chan poster", appears in Engen and Vatter (2021). For "The Haruhi Problem" specifically (the case for 14 symbols), the current lower and upper bound are 93,884,313,611 and 93,924,230,411, respectively. This means that watching the series in every possible order would require about 4.3 million years.

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, science fiction author and mathematician Greg Egan devised an algorithm to produce superpermutations of length n! + (n−1)! + (n−2)! + (n−3)! + 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 (n! + (n−1)! + (n−2)! + (n−3)! + n − 3) − 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. The current best lower bound (see section above) for n = 7 is still 5884.

See also

• Superpattern, a permutation that contains each permutation of n symbols as a permutation pattern
• De Bruijn sequence, a similar problem with cyclic sequences

Further reading

• Ashlock, Daniel A.; Tillotson, Jenett (1993), "Construction of small superpermutations and minimal injective superstrings", Congressus Numerantium, 93: 91–98, Zbl 0801.05004
• Anonymous 4chan Poster; Houston, Robin; Pantone, Jay; Vatter, Vince (October 25, 2018). "A lower bound on the length of the shortest superpattern" (PDF). On-Line Encyclopedia of Integer Sequences.{{cite journal}}: CS1 maint: numeric names: authors list (link)

External links

• The Minimal Superpermutation Problem - Nathaniel Johnston's blog
• Grime, James. "Superpermutations - Numberphile" (video). YouTube. Brady Haran. Retrieved 1 February 2018.
• The original 4chan post on /sci/, archived on warosu.org
• Tweet by Robin Houston, which brought attention to the 4chan post
• Article about the problem of finding short superpermutations in Quanta Magazine