OFFSET
1,3
COMMENTS
Sequence A180632 gives the row lengths and more information about superpermutations, i.e., strings over a finite alphabet that contain all permutations thereof as a substring.
In March 2014, Ben Chaffin showed that minimal superpermutations of order n = 5 have length 153, and found all 8 distinct superpermutations of this kind; the (non-palindromic) lexicographically first one is row 5 of this table. For n = 6, Robin Houston has found a few months later several superpermutations of length 872 (one less than the previously conjectured minimal length), but we still don't know which is the shortest (and/or lexico-first) superpermutation for that case.
LINKS
Robin Houston, Tackling the Minimal Superpermutation Problem, arXiv:1408.5108 [math.CO], 2014.
Nathaniel Johnston, Non-uniqueness of minimal superpermutations, arXiv:1303.4150 [math.CO], 2013; Discrete Math., 313 (2013), 1553-1557.
Wikipedia, Superpermutation
FORMULA
For n < 5, row n results from row n - 1 by making the list of all substrings which are permutations, duplicating them and inserting (n) between the two copies, and merging them together again, with overlap reduced as much as possible.
EXAMPLE
The table starts:
n | SP[n]
----+---------------------------
1 | (1)
2 | (1, 2, 1)
3 | (1, 2, 3, 1, 2, 1, 3, 2, 1)
4 | (1, 2, 3, 4, 1, 2, 3, 1, 4, 2, 3, 1, 2, 4, 3, 1, 2,
| 1, 3, 4, 2, 1, 3, 2, 4, 1, 3, 2, 1, 4, 3, 2, 1)
5 | (1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 1, 2, 5, 3, 4, 1,
| 2, 3, 5, 4, 1, 2, 3, 1, 4, 5, 2, 1, 3, 4, 2, 5, 1, 3, 4,
| 2, 1, 5, 3, 4, 2, 1, 3, 5, 4, 2, 1, 3, 4, 5, 2, 1, 4, 3,
| 5, 2, 1, 4, 5, 3, 2, 1, 4, 5, 2, 3, 1, 4, 2, 5, 3, 1, 4,
| 2, 3, 5, 1, 4, 2, 3, 1, 5, 4, 2, 3, 1, 2, 4, 5, 3, 1, 2,
| 4, 3, 5, 1, 2, 4, 3, 1, 5, 2, 4, 3, 1, 2, 5, 4, 3, 2, 1,
| 5, 4, 3, 2, 5, 1, 4, 3, 2, 5, 4, 1, 3, 2, 4, 5, 1, 3, 2,
| 4, 1, 5, 3, 2, 4, 1, 3, 5, 2, 4, 1, 3, 2, 5, 4, 3, 1, 2)
One can consider an initial row 0 of length 0, producing row 1 as concatenation of (), (1), ().
Row 2 results from duplicating row 1 with (2) inserted in the middle.
Row 3 results from making the list of all permutations in row 2, ((1, 2), (2, 1)), then duplicating these and inserting (3), i.e.: ((1, 2, 3, 1, 2), (2, 1, 3, 2, 1)), then merging together with the second instance of the overlapping '2' removed in the middle.
Row 4 results in the same way from row 3, where the permutations are all length 3 substrings except for the middle (1, 2, 1).
Applying the same procedure to row 4 yields a superpermutation of {1, ..., 5} of minimal length 153 which is palindromic as the earlier ones, but not the lexicographically first one, which is given above.
PROG
A332089_row(n)={n>5 && error("not yet implemented"); digits(fromdigits([d-37| d<-Vecsmall(["&", "&:", "&<12:", "&<N<3<1P12O2=2:P:", "&<R1G4<N>G1HN<3Y2OXG" ":ZO2[:GY3H:RE3YDOZ3<XOD[<1RD=H1P4=D>P:[EXP>NER2=4ENH=2>P1"][n])], 100))}
CROSSREFS
KEYWORD
nonn,hard,tabf
AUTHOR
M. F. Hasler, Jul 31 2020
STATUS
approved