Superpermutation

Last updated
The distribution of permutations in a 3-symbol superpermutation Superpermutation distribution.png
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.

Contents

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]

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 Superpermutations.jpg
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.

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. [3] In reference to the Japanese anime series The Melancholy of Haruhi Suzumiya , the problem was presented on the imageboard as "The Haruhi Problem": [4] 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. [3] 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] A published version of this proof, credited to "Anonymous 4chan poster", appears in EngenandVatter ( 2021 ). [7] 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. [3] This means that watching the series in every possible order would require about 4.3 million years. [8]

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, [9] science fiction author and mathematician 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 = 7 is still 5884.

See also

Further reading

Related Research Articles

Greg Egan is an Australian science fiction writer and mathematician, best known for his works of hard science fiction. Egan has won multiple awards including the John W. Campbell Memorial Award, the Hugo Award, and the Locus Award.

<span class="mw-page-title-main">Tower of Hanoi</span> Mathematical game or puzzle

The Tower of Hanoi is a mathematical game or puzzle consisting of three rods and a number of disks of various diameters, which can slide onto any rod. The puzzle begins with the disks stacked on one rod in order of decreasing size, the smallest at the top, thus approximating a conical shape. The objective of the puzzle is to move the entire stack to one of the other rods, obeying the following rules:

  1. Only one disk may be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
  3. No disk may be placed on top of a disk that is smaller than it.

700 is the natural number following 699 and preceding 701.

<span class="mw-page-title-main">Pancake sorting</span> Mathematics problem

Pancake sorting is the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it. A pancake number is the minimum number of flips required for a given number of pancakes. In this form, the problem was first discussed by American geometer Jacob E. Goodman. A variant of the problem is concerned with burnt pancakes, where each pancake has a burnt side and all pancakes must, in addition, end up with the burnt side on bottom.

1729 is the natural number following 1728 and preceding 1730. It is notably the first nontrivial taxicab number.

213 is the number following 212 and preceding 214.

de Bruijn sequence Cycle through all length-k sequences

In combinatorial mathematics, a de Bruijn sequence of order n on a size-k alphabet A is a cyclic sequence in which every possible length-n string on A occurs exactly once as a substring (i.e., as a contiguous subsequence). Such a sequence is denoted by B(k, n) and has length kn, which is also the number of distinct strings of length n on A. Each of these distinct strings, when taken as a substring of B(k, n), must start at a different position, because substrings starting at the same position are not distinct. Therefore, B(k, n) must have at leastkn symbols. And since B(k, n) has exactlykn symbols, de Bruijn sequences are optimally short with respect to the property of containing every string of length n at least once.

225 is the natural number following 224 and preceding 226.

In computer science, the longest increasing subsequence problem aims to find a subsequence of a given sequence in which the subsequence's elements are sorted in an ascending order and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous or unique. The longest increasing subsequences are studied in the context of various disciplines related to mathematics, including algorithmics, random matrix theory, representation theory, and physics. The longest increasing subsequence problem is solvable in time where denotes the length of the input sequence.

5 (five) is a number, numeral and digit. It is the natural number, and cardinal number, following 4 and preceding 6, and is a prime number. It has garnered attention throughout history in part because distal extremities in humans typically contain five digits.

In the mathematical study of permutations and permutation patterns, a superpattern or universal permutation is a permutation that contains all of the patterns of a given length. More specifically, a k-superpattern contains all possible patterns of length k.

In-place matrix transposition, also called in-situ matrix transposition, is the problem of transposing an N×M matrix in-place in computer memory, ideally with O(1) (bounded) additional storage, or at most with additional storage much less than NM. Typically, the matrix is assumed to be stored in row-major or column-major order.

In mathematics, the Golomb–Dickman constant arises in the theory of random permutations and in number theory. Its value is

<span class="mw-page-title-main">Synchronizing word</span>

In computer science, more precisely, in the theory of deterministic finite automata (DFA), a synchronizing word or reset sequence is a word in the input alphabet of the DFA that sends any state of the DFA to one and the same state. That is, if an ensemble of copies of the DFA are each started in different states, and all of the copies process the synchronizing word, they will all end up in the same state. Not every DFA has a synchronizing word; for instance, a DFA with two states, one for words of even length and one for words of odd length, can never be synchronized.

In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of entries representing the result of applying the permutation to the sequence 123...; for instance the sequence 213 represents the permutation on three elements that swaps elements 1 and 2. If π and σ are two permutations represented in this way, then π is said to contain σ as a pattern if some subsequence of the entries of π has the same relative order as all of the entries of σ.

In the study of permutation patterns, there has been considerable interest in enumerating specific permutation classes, especially those with relatively few basis elements. This area of study has turned up unexpected instances of Wilf equivalence, where two seemingly-unrelated permutation classes have the same numbers of permutations of each length.

In number theory, the complexity of an integer is the smallest number of ones that can be used to represent it using ones and any number of additions, multiplications, and parentheses. It is always within a constant factor of the logarithm of the given integer.

In the theory of permutation patterns, a skew-merged permutation is a permutation that can be partitioned into an increasing sequence and a decreasing sequence. They were first studied by Stankova (1994) and given their name by Atkinson (1998).

In the mathematics of permutations, a layered permutation is a permutation that reverses contiguous blocks of elements. Equivalently, it is the direct sum of decreasing permutations.

In mathematics and computer science, the sorting numbers are a sequence of numbers introduced in 1950 by Hugo Steinhaus for the analysis of comparison sort algorithms. These numbers give the worst-case number of comparisons used by both binary insertion sort and merge sort. However, there are other algorithms that use fewer comparisons.

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. S2CID   12018639. Zbl   1368.05004 . Retrieved March 16, 2014.
  2. 1 2 3 4 5 6 Egan, Greg (20 October 2018). "Superpermutations". gregegan.net. Retrieved 15 January 2020.
  3. 1 2 3 Griggs, Mary Beth. "An anonymous 4chan post could help solve a 25-year-old math mystery". The Verge.
  4. ↑ Anon, - San (September 17, 2011). "Permutations Thread III ニア愛". Warosu.
  5. 1 2 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.{{cite web}}: CS1 maint: numeric names: authors list (link)
  7. ↑ Engen, Michael; Vatter, Vincent (2021), "Containing all permutations", American Mathematical Monthly , 128 (1): 4–24, arXiv: 1810.08252 , doi: 10.1080/00029890.2021.1835384
  8. ↑ Spalding, Katie (2018-10-30). "4chan Just Solved A Decades-Old Mathematical Mystery". IFLScience. Retrieved 2023-10-05.
  9. ↑ Aaron, Williams (2013). "Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2)". arXiv: 1307.2549v3 [math.CO].
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.