HOME

TheInfoList



OR:

In
combinatorial Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
mathematics, a superpermutation on ''n'' symbols is a string that contains each permutation of ''n'' symbols as a
substring In formal language theory and computer science, a substring is a contiguous sequence of characters within a string. For instance, "''the best of''" is a substring of "''It was the best of times''". In contrast, "''Itwastimes''" is a subsequenc ...
. While
trivial Trivia is information and data that are considered to be of little value. It can be contrasted with general knowledge and common sense. Latin Etymology The ancient Romans used the word ''triviae'' to describe where one road split or forked ...
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. 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 (after the bold 2): 123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321 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 ''n''th 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 Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
where each permutation is a vertex and every permutation is connected by an edge. Each edge has a
weight In science and engineering, the weight of an object is the force acting on the object due to gravity. Some standard textbooks define weight as a vector quantity, the gravitational force acting on the object. Others define weight as a scalar qua ...
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 In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
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 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 tightened 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 4chan is an anonymous English-language imageboard website. Launched by Christopher "moot" Poole in October 2003, the site hosts boards dedicated to a wide variety of topics, from anime and manga to video games, cooking, weapons, television, ...
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 is hand-drawn and computer-generated animation originating from Japan. Outside of Japan and in English, ''anime'' refers specifically to animation produced in Japan. However, in Japan and in Japanese, (a term derived from a shortening of ...
series ''
The Melancholy of Haruhi Suzumiya is a Japanese light novel series written by Nagaru Tanigawa and illustrated by Noizi Ito. It was first published in 2003 by Kadokawa Shoten in Japan with the novel ''The Melancholy of Haruhi Suzumiya'', and has since been followed ...
'', 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 The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to t ...
(OEIS). A published version of this proof, credited to "Anonymous 4chan poster", appears in . 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 million years.


Upper bounds

On 20 October 2018, by adapting a construction by Aaron Williams for constructing
Hamiltonian path In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
s through the
Cayley graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cay ...
of the
symmetric group In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group ...
, Science Fiction author and mathematician
Greg Egan Greg Egan (born 20 August 1961) is an Australian science fiction writer and amateur 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, ...
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 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 ...
, a permutation that contains each permutation of ''n'' symbols as a
permutation pattern 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 digits representing the result of applying the p ...
*
De Bruijn sequence 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'' subseq ...
, a similar problem with cyclic sequences


Further reading

* *


References


External links


The Minimal Superpermutation Problem - Nathaniel Johnston's blog
* {{cite web, last1=Grime, first1=James, title=Superpermutations - Numberphile, url=https://www.youtube.com/watch?v=wJGE4aEWc28, website=YouTube, publisher=
Brady Haran Brady John Haran (born 18 June 1976) is an Australian-British independent filmmaker and video journalist who produces educational videos and documentary films for his YouTube channels, the most notable being ''Periodic Videos'' and '' Numbe ...
, accessdate=1 February 2018, format=video
The 4chan post on /sci/
archived on warosu.org
Tweet
by Robin Houston, which brought attention to the 4chan post Combinatorics on words Enumerative combinatorics Permutations