The shortest string holding every ordering

No cycle can show every ordering of three symbols as a window of three: a window holding each symbol once forces the next symbol to repeat the one just dropped, so a cyclic arrangement goes round in a loop of length three instead of visiting all six orderings. The fix there was shorthand — windows of one symbol fewer, the missing one implied. The other fix keeps every symbol and gives up the cycle: write a straight string, as short as possible, in which every ordering appears somewhere as a block of consecutive symbols.

Such a string is a superpermutation. For three symbols the shortest has nine symbols, 123121321, and for four symbols the shortest has thirty-three.

The string has thirty windows of four. Twenty-four of them are the twenty-four orderings, each exactly once, and six are wasted — they repeat a symbol and are not orderings at all. A string of twenty-seven symbols would have exactly twenty-four windows, and if they could all be different orderings that would be the end of the matter; the question is why six windows have to be thrown away, and how the waste grows with the number of symbols. For four symbols the answer is 33, and it is unique: every shortest string is this one with the symbols renamed. For five the answer is 153. For six nobody knows.

A tour of the orderings #

The problem is a route-planning problem in disguise. Two orderings can follow each other in a string as closely as they overlap: 1234 can be followed by 2341 with one new symbol, because their last three and first three agree, or by 3412 with two, or by 4123 with three. So write down every ordering, let the cost of going from one to another be the number of new symbols it takes, and the shortest superpermutation is the cheapest route that visits every ordering once — plus the $n$ symbols of the first ordering. It is the travelling salesman’s problem on the $n!$ orderings, with distances one to $n$.

That framing explains both why the problem is hard and how the record for six symbols was eventually broken: Robin Houston found his string in 2014 by handing the problem to a program written for travelling salesmen, LKH, after the obvious constructions had stalled. Exact solvers for the travelling salesman’s problem prove optimality by pairing a good tour with a lower bound from a linear programme, and that bound can be off by as much as a third on bad instances; for the 720 orderings of six symbols no such proof has been found. It also says where to look for structure. The cheap steps, of cost one, move the first symbol to the end: 1234 to 2341 to 3412 to 4123 and back to 1234. They form rings of $n$ rotations, and the $n!$ orderings fall into $(n-1)!$ such rings.

The shortest string walks three steps round each ring — never the fourth, which would return to an ordering already used — and then jumps to the next ring. Five of the six rings have to be entered from outside, and an entry costs at least two symbols. Eighteen steps of one, four of two and a single step of three add up to $4 + 18 + 8 + 3 = 33$. In the shortest string each ring is used in a single run of three cost-one steps — eighteen of them for six rings — so every ring is entered exactly once. The wasted windows are exactly the extra symbols of the expensive steps: a step of cost two passes one window that is not an ordering, a step of cost three passes two.

Orderings as a graph with symmetry #

The cost-one steps have an algebraic description that explains the rings. Moving the first symbol of an ordering to the end is the same operation whichever ordering it is applied to, so it is a single permutation $r$ acting on positions, and the ring through any ordering is that ordering followed by $r$, $r^2$, $r^3$ and back. The cost-two step that jumps between rings is another fixed operation: move the first two symbols to the end, swapped. Together the two operations generate every ordering from any other, which makes the orderings the vertices of a Cayley graph of the symmetric group, and a superpermutation of minimal length is a cheap route through it.

Routes through every vertex of such a graph are an old subject. Listing every ordering so that consecutive ones differ by a single swap of neighbouring symbols — the bell-ringers’ plain changes, rediscovered by Steinhaus, Johnson and Trotter in the 1960s — is a route through the Cayley graph of adjacent swaps, the permutation counterpart of a walk that changes one bit at a time. László Lovász asked in 1969 whether every connected graph with this much symmetry has a route through all its vertices. Every case checked has one, though in four known graphs — the Petersen graph, Coxeter’s graph and two relatives — the route cannot be closed into a tour, and none of the four is a Cayley graph. For superpermutations the existence of a route is easy; the difficulty is entirely in making it cheap, because the graph’s two kinds of edge have different prices.

The string every rule writes #

There is a classical recursive construction. Take the shortest string for $n - 1$ symbols; for each ordering of $n - 1$ symbols in the order it appears there, write it, then the new symbol $n$, then the ordering again; and glue the pieces with as much overlap as they allow. From 1 it builds 121, then 123121321, then the 33-symbol string, and each step multiplies the work by about $n$.

The costs show the recursion as a bar code. For $n$ symbols, the new symbol is threaded through each of the old string’s orderings in turn, producing runs of $n - 1$ cheap steps; between runs, the string pays what the old string paid between its orderings, plus one for the new symbol. Adding everything up gives

$$1! + 2! + 3! + \cdots + n!,$$

which is 9, 33, 153, 873 and 5,913 for three to seven symbols. Why the construction contains every ordering is a short argument. The block $w\,n\,w$ has $2n - 1$ symbols, and its $n$ windows of length $n$ are the $n$ rotations of $w\,n$. Any ordering of $n$ symbols, rotated until the symbol $n$ comes last, has the form $w\,n$ for some ordering $w$ of the other $n - 1$ — and every such $w$ appears in the old string, so it gets a block, and the block contains every rotation of $w\,n$, the original ordering among them. A greedy rule — at every moment, write the fewest symbols that complete an ordering not yet seen, choosing the smallest when there is a tie — produces exactly the same string, and the figures confirm it for every $n$ up to seven. Two different ideas, recursion and greed, land on the same answer, which is the kind of agreement that makes a formula feel inevitable. Daniel Ashlock and Jenett Tillotson conjectured in 1993 that it is always the shortest. The same coincidence of a natural rule and an optimal answer happens for de Bruijn sequences, where writing every necklace in lexicographic order gives the same sequence as the greedy rule prefer the larger symbol; there the greedy rule is provably optimal, because a de Bruijn sequence cannot be shorter than the number of words, and every greedy sequence achieves that.

The cost-one steps are the same object that makes every word appear once in a de Bruijn cycle: an overlap of $n - 1$ symbols between consecutive windows. A de Bruijn cycle never has to waste a window, because every word of $n - 1$ symbols can be extended in a way that produces a new word; with orderings the extension is forced, and that forcing is what turns a cycle with no waste into a string with $(n-1)! + (n-2)! + \cdots$ wasted windows.

How many orderings fit in a given length #

A finer question than the shortest complete string is how many orderings a string of each length can hold, and for four symbols it can be answered exhaustively.

The best count climbs by one with every symbol for a while — four orderings in seven symbols, by going once round a ring — and then stalls, because the next ordering must come from another ring and costs two symbols. The stalls arrive at lengths 8, 13, 18, 21, 26 and 29, which are the six places where some string of maximal content has to change rings. The classical string keeps pace with the best possible count at every length except four: around its single three-symbol jump it falls one ordering behind strings that arrange their ring changes differently, and then catches up. A string that is shortest overall is not automatically the best at every stage.

The formula, the bound and the record #

For four symbols an exhaustive search settles everything. For five, Ben Chaffin’s exhaustive search in 2014 confirmed that 153 is the shortest — and found that, unlike four, five symbols have several genuinely different shortest strings, not just renamings of one. Then six broke the pattern.

Robin Houston’s string for six symbols has 872 symbols, one fewer than the formula’s 873, and with it the conjecture that the formula is always optimal fell. In 2018 Greg Egan constructed superpermutations of length $n! + (n-1)! + (n-2)! + (n-3)! + n - 3$ for every $n$, beating the formula for every $n$ from seven up. So the formula is not the truth for large $n$, and its failure at six was the first sign of a gap that widens.

The lower bound has a stranger history. In 2011 an anonymous user of an internet forum, asked how many episodes one would need to watch to see the fourteen episodes of an animated series in every possible order, posted a short argument that any superpermutation on $n$ symbols has at least $n! + (n-1)! + (n-2)! + n - 3$ symbols. The argument was noticed years later, checked carefully by Houston, Jay Pantone and Vince Vatter, and found to be correct. It gives 9 and 33 for three and four symbols, matching the truth exactly, 152 for five where the truth is 153, and 867 for six — so for six the shortest superpermutation is somewhere between 867 and 872, and nobody knows where. For the original question, the fourteen episodes, the bound says at least 93,884,313,611 episodes must be watched, and Egan’s construction shows that 93,924,230,411 are enough — a difference of about forty million episodes, and at half an hour each, a viewing schedule of a little over five million years either way.

Waste that becomes negligible #

Measured against the number of orderings, the waste shrinks. The formula’s length divided by $n!$ is $1 + 1/n + 1/(n(n-1)) + \cdots$, which tends to one, and the anonymous lower bound and Egan’s construction agree with it in the first three terms: every shortest superpermutation has length $n!\,(1 + 1/n + 1/(n(n-1)))$ to that accuracy. So for large $n$ almost every window is a new ordering, and the fraction wasted is about $1/n$ — one ring change for every ring, each ring having $n$ orderings.

That is a different kind of statement from the one about de Bruijn sequences, where the waste is exactly nothing for every $n$. Here the waste is a vanishing fraction of a quantity that grows faster than any power: at ten symbols there are more than three and a half million orderings, and a shortest superpermutation wastes several hundred thousand windows on them even if the leading terms are all that matter. The open questions are about the fourth term of the expansion and beyond, which is where the formula, the bound and the constructions start to disagree, and which is invisible in the ratio but decisive in the count.

Settling four by search #

The claim that 33 is shortest for four symbols, and that the string is unique up to renaming, rests on a search, and the search is small enough to show.

Starting from 1234 loses nothing, because renaming the symbols can make any string start with any ordering. From there a branch-and-bound search builds visiting orders one ordering at a time and abandons any partial order that, even if every remaining ordering cost only one symbol, would already be too long. Bounding at 35 symbols leaves under ten million partial orders to examine, and bounding at 33 leaves about a third of a million. The result is that exactly one visiting order from 1234 reaches 33, so the 24 shortest strings are the 24 renamings of one string.

The shortest string has a symmetry of its own that the search confirms rather than assumes: it is a palindrome, reading the same backwards. Reversing any superpermutation gives another of the same length, since reversing a window reverses an ordering and the reversed orderings are again all the orderings; uniqueness up to renaming then forces the reversal to be a renaming of the original, and for this string the renaming is the identity.

The counts just above the minimum say how special the shortest string is. Twenty-eight visiting orders reach 34 and three hundred and sixteen reach 35, so a search that settles for one symbol more has dozens of answers to choose from, and one that wants the best has exactly one. For five symbols the same search is far larger, because there are 120 orderings instead of 24 and the number of near-optimal routes multiplies; for six, with 720 orderings, exhaustive search is out of reach, which is why 867 to 872 is still a range.

What the pictures cannot settle #

The rings, the bar codes and the densities are drawn for four and five symbols, where everything can be listed. They show the structure that the classical construction exploits, and they cannot show the structure that beats it, because the strings that beat the formula exist only from six symbols up, at 872 symbols and beyond, where no figure can display their windows legibly and no search can certify them as best. The figures make the formula look inevitable, and it is not; that is a fact the small cases hide, and it is the reason a string of 872 symbols was a surprise.

The lower bound is a theorem, and nothing on this page proves it; its argument counts the rings and the larger structures above them more cleverly than the simple observation that each new ring costs two. The search figures, by contrast, are proofs for four symbols — exhaustive and exact — but say nothing about five or more.

Still open: the shortest string for six symbols #

The shortest superpermutation on six symbols has between 867 and 872 symbols, and which it is remains unknown. The upper end is Houston’s string and many relatives found since; the lower end is the anonymous bound, which is not believed to be tight. Closing the gap needs either a cleverer argument or a search through a space of routes on 720 orderings that is enormous even with good pruning. For larger $n$ the gap between Egan’s construction and the anonymous bound grows like $(n-3)!$ in absolute terms, and the right asymptotic length, beyond its leading terms $n! + (n-1)! + (n-2)!$, is open too.

Related questions are open as well: the shortest string containing every ordering when the string may wrap round as a cycle, and the shortest one when windows may be read in either direction. In every version the de Bruijn ideal — every window useful — is impossible, and the question is exactly how much waste the forcing imposes.

Waste forced by the windows #

A superpermutation is a cheapest tour of the $n!$ orderings, in which a step costs as many new symbols as the next ordering fails to overlap the last. Cheap steps go round rings of rotations and expensive ones jump between rings, and the classical string — written alike by recursion and by greed — pays $1! + 2! + \cdots + n!$. That is optimal for four symbols, uniquely, and for five, and then it is not: six symbols fit in 872, the anonymous lower bound says at least 867, and the truth is somewhere between.