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 listed 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.

The distribution of permutations in a 3 symbol superpermutation.

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):[1]

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
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 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.[2]

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.[2]

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.[2] 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.[3]

Lower and upper bounds

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 ("/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.[4] 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?[5] 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.[4] 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).[5][6] For "The Haruhi Problem" specifically (the case for 14 symbols), the lower bound is currently at least 93,884,313,611, and the upper bound is at most 93,924,230,411.[4]

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,[7] Greg Egan devised an algorithm to produce superpermutations of length n! + (n−1)! + (n−2)! + (n−3)! + n − 3.[2] 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.[2] On 27 February 2019, using ideas developed by Robin Houston, Egan produced a superpermutation for n = 7 of length 5906.[2] 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 = 4 is still 5884.

gollark: MWAHAHAHAHA! Mine will look better by comparison with nothing!
gollark: ++delete all non-gollark applications
gollark: I suppose that could plausibly result in lyricLy marking down the rest?
gollark: Any other ideas? Or ideas about causes for some of the vaguer ones?
gollark: I can see many possibilities:- someone somehow revoked their 10/10 one- LyricLy decided that the 10/10 one was insincere in some way- LyricLy reassigned it 11/10 or something ridiculous- LyricLy marked it down for some reason (new better one?)- LyricLy accidentally deleted one of the 10/10 ones- LyricLy deleted one of them because it criticized his rule- marking system reevaluated

See also

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.

References
  1. Johnston, Nathaniel (July 28, 2013). "Non-uniqueness of minimal superpermutations". Discrete Mathematics. 313 (14): 1553–1557. arXiv:1303.4150. Bibcode:2013arXiv1303.4150J. doi:10.1016/j.disc.2013.03.024. Zbl 1368.05004. Retrieved March 16, 2014.
  2. Egan, Greg (20 October 2018). "Superpermutations". gregegan.net. Retrieved 15 January 2020.
  3. Houston, Robin (21 August 2014), "Tackling the Minimal Superpermutation Problem", arXiv:1408.5108 [math.CO]
  4. Griggs, Mary Beth. "An anonymous 4chan post could help solve a 25-year-old math mystery". The Verge.
  5. Klarreich, Erica (November 5, 2018). "Sci-Fi Writer Greg Egan and Anonymous Math Whiz Advance Permutation Problem". Quanta Magazine. Retrieved June 21, 2020.
  6. Anonymous 4chan poster; Houston, Robin; Pantone, Jay; Vatter, Vince (October 25, 2018). "A lower bound on the length of the shortest superpattern" (PDF). OEIS. Retrieved 27 October 2018.
  7. Aaron, Williams. "Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2)". arXiv:1307.2549v3.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.